Message: 4 Date: Fri, 09 May 2003 23:36:33 +0200 From: Raphael Manfredi Subject: FYI: gtk-gnutella now implements PARQ GDFers, It is my pleasure to inform you that PARQ has been finally successfully implemented in GTKG. Jeroen Asselman is the author of that implementation, based on the specs I published 10 months ago. Although the implementation is now fairly complete, including support for the legacy "active queueing", it still has some rough edges. In particular, the management of the queue entry obsolescence is not fully satisfactory. Nonetheless, I wanted to report that PARQ adds great fairness to the downloading process. Since the queue is persistent, people don't loose their slot when GTKG goes down. Moreover, the QUEUE callback ensures that downloads can resume at their slot position even when the connection is broken. The fact that PARQ works transparently for clients unaware of it is also a great benefit, although those clients will lack the most advanced features (like the ability to understand QUEUE callbacks). In short, I encourage you all to give PARQ a shot. When Jeroen is fully done with the implementation, we will publish an Appendix to PARQ describing the additional logic that GTKG implements, although not strictly part of the specs. You will have noticed that PARQ is more complex to implement than the "active queueing" feature, but I think viewing it work so nicely is a reward. Thank you Jeroen for making PARQ a reality on Gnutella. Raphael ________________________________________________________________________ Date: Fri, 09 May 2003 23:12:25 -0000 From: "Vinnie" Subject: Re: FYI: gtk-gnutella now implements PARQ --- In the_gdf@yahoogroups.com, Raphael Manfredi wrote: You will have noticed that PARQ is more complex to implement than the "active queueing" feature, but I think viewing it work so nicely is a reward. I would love to hear Dave's analysis of "PARQ"... ________________________________________________________________________ >>>>> I add the PARQ documentation here. be aware, that this is not the finished Version. Later changes and suggestions aren't cited for space reasons. - Draketo <<<<< ________________________________________________________________________ Message: 2 Date: Sat, 10 May 2003 19:42:51 +0200 From: Raphael Manfredi Subject: PARQ updated I have updated the PARQ documentation. For your convenience, here it is again, but it's also in the Files section of the GDF (under Proposals / QUEUE). For changes since the original publication, look at the Appendix at the end. Raphael ------------------------------------------------------------------------ Passive/Active Remote Queueing Version 1.0.a Raphael Manfredi August, 14th 2002 May, 10th, 2003 1. Introduction This proposal is a formalization of my previous Queueing proposal, which was in turn derived from the original proposal from Mike Green. It has been refined to take into account the feedback I got from the GDF, as well as my own comments to another queueing proposal from Christopher Rohrs. The aim of remote queueing is to have a servent serving a file (aka, the "server") enqueue a request from a servent requesting a file (aka, the "client") when the server has run out of upload slots. This queueing must satisfy the following properties: * Fairness: first come, first serve, provided the client plays by the rules. * Monitoring: the client side must be able to monitor progress. * Remanence: the queue must survive a servent shutdown, either on the client side or on the server side, provided the servent comes back "quickly". * Legacy: older servents not aware of PARQ must not be penalized and must still get their share of slots. This also participates to Fairness. A few comments on those properties: Fairness is obvious. Monitoring ensures that the client can see the evolution of its queued slot on the server, which helps the end-user decide whether it should pursue further or "cancel" the download. Remanence allows the client or server to become unavailable for a short period of time (max. 5 minutes) and yet not perturb the queue. This property is valuable for modem users (this includes DSL users), which can experience a connection drop, and servent developers who can have their servent crash in the middle of an experiment. Finally, Legacy ensures that in a world of queueing servers, a client not aware of PARQ can still be allowed to get slots, although it will not be able to get the complete PARQ experience, of course. 2. Definitions and Principles PARQ maintains an arbitrary long queue (typically 5000 entries or more) which is split into two parts: Aq. Asynchronous queue, the largest part. Those are the newest entries added to the queue, and are far away from being scheduled. The queue is said to be asynchronous because the connection between the server and the client is not maintained. Sq. Synchronous queue, the smallest part. Those are the entries close to be able to get an uploading slot. The connection between the server and the client is maintained. Typically, Sq will hold the top 50 entries or so, and Aq will hold the remaining 4950 ones. As time goes by, an entry first made in Aq will gradually moves to Sq, and then is allowed the uploading slot. Naturally, if Sq is almost empty, the entry is initially made there, not to Aq, which starts filling when Sq is full. Each entry is identified by a random GUID allocated when it enters the server queue. This GUID acts as a "token" and is used by the server to recognize the entry. This is espcially useful for Aq entries, but Sq entries can occasionally make use of this GUID (for Remanence, or for Legacy clients which are queued without knowing it). An queued slot is said to be "actively queued" if the client is aware of PARQ and knows that its request is in the queue. Otherwise, the slot is said to be "passively queued", which means the client is unaware of it (legacy clients). It follows that only actively queued entry actually use the Sq. All passively queued entry, use the Sq slots like the Aq ones, since the client is unaware of it. 3. Required Features In order to use PARQ actively, the client must support HTTP/1.1 persistent connections. If an active client is connected to the server, and the connection is broken for any reason, it can reconnect within the next 300 seconds and keep its slot in the queue (Remanence effect). In order to use PARQ passively, the client need either support the Retry-After: header in HTTP responses, and strictly honour it instead of its internal retry timer. Only the Retry-After: for of the header is used, for convenience. If the client does not support Retry-After:, as many legacy servents do, the client only needs to retry the download on 503 before the next 300 seconds. Optionally, non-firewalled clients that support PARQ can also support a new form of request that can be used by the server as a callback. It is similar to a GIV request sent by the server to the client when a PUSH is received. It is named "QUEUE" and will be detailed in section 4. 4. Active Queueing This section presents the active queueing, i.e. only addresses clients that are aware of PARQ. PARQ-compliance is indicated by the client through the following header in the HTTP request: X-Queue: 1.0 which indicates that the servent will understand the queueing protocol and the replies from the PARQ-compliant server. An initial request/answer from the client will result in the following HTTP exchange: GET /resource HTTP/1.1 User-Agent: blah X-Queue: 1.0 X-Node: 13.4.5.6:4567 HTTP/1.1 503 Queued Server: blah X-Queue: 1.0 X-Queued: position=1503; length=1840; ETA=4200; lifetime=3600; ID=6a074979f3201edbf323b6425fef4a53 Connection: close Retry-After: 600 The "X-Node" in the request indicates the client is not firewalled and provides the address and port where the server can make its QUEUE callback, if necessary (more on this later). The server tells its PARQ level of support via its own X-Queue header. Even if the server supports a more recent version (say 1.3), it will always downgrade its reply to match that of the client. The "X-Queued" header of the reply indicates that the request was asynchronously queued. The general syntax of the X-Queued: header is a list of var=value settings, each separated by ';'. The spaces after each ';' are optional. Variables are case-insensitive (i.e. "ID" and "id" are the same). The meaning of each variable is: "position": This is the current queue position (here 1503). Also known as the current queue slot. "length": The current queue length (here 1840 requests are queued). "ETA": The ETA (Estimated Time of Arrival) for the item to reach an upload slot, in seconds. It can be estimated by summing the whole size of the last files requested at each queue position, and assuming an optimal transfer rate equal to the maximum upload bandwidth. (here, 4200 seconds, a totally non-realistic figure). "lifetime": time during which the server will hold the queue position. The server expects a new request to come before the lifetime expires. (here, a new request must be made before the next 3600 seconds). However, the minimum retry blackout period indicated by Retry-After MUST be honoured by the client (here, 600 seconds). "ID": The unique queue ID (pure random number). It must be remembered and given out by the client within further requests to identify the queued item. If the client does not re-issue the request before "lifetime", and provided there was an X-Node given, then the server will contact the client at the specified IP:port and will give it the following request: QUEUE 6a074979f3201edbf323b6425fef4a53 45.56.67.78:1234\r\n To "cancel" the request, the client simply stops sending requests and ignores the QUEUE callbacks, which will cause the slot to be freed. The format of the QUEUE line is: QUEUE :\r\n The IP and port are those of the server. It is necessary to communicate them again because the server might have changed its IP address since the client started the queueing, and if we don't refresh it, the client will have no way to contact the server back again: it will only be able to reply to QUEUE requests. In order to maintain its queue position, the client MUST reply with: GET /resource HTTP/1.1 User-Agent: blah X-Node: 13.4.5.6:4567 X-Queue: 1.0 X-Queued: position=1503; ID=6a074979f3201edbf323b6425fef4a53 HTTP/1.1 503 Queued Server: blah X-Queue: 1.0 X-Queued: position=1501; length=3500; ETA=4100; lifetime=3600; ID=6a074979f3201edbf323b6425fef4a53 Connection: close Retry-After: 600 This is identical to any client-generated requery made by the client. Note that even when replying to a QUEUE request, the ID MUST be given in the request. This simplifies the implementation on the server side. (and the server will again reply with the same ID, the aim being to avoid special-casing the processing of those headers as much as possible). The X-Queued header in the request simply shows the server that the client at this IP:port knows the last slot number that was returned for this entry, and is therefore the proper client. If there is a mismatch, the corresponding slot is immediately freed. The QUEUE callback is useful when the server is firewalled and the client is not. Otherwise, the client will make the request after the time given by the Retry-After, and the server will never make the callback. Any PARQ-compliant client MUST honour the Retry-After. Sending the request too soon will cause the slot to be freed. When the slot number is low enough to enter the Synchronous Queue (Sq), the HTTP exchanges becomes totally different. Let's take a requery as an example, but things would be totally similar for an initial request: GET /resource HTTP/1.1 User-Agent: blah X-Node: 13.4.5.6:4567 X-Queue: 1.0 X-Queued: position=53; ID=6a074979f3201edbf323b6425fef4a53 HTTP/1.1 503 Queued Server: blah X-Queue: 1.0 X-Queued: position=14; length=4300; ETA=2100; ID=6a074979f3201edbf323b6425fef4a53 Retry-After: 290 <290 seconds later> GET /resource HTTP/1.1 User-Agent: blah X-Node: 13.4.5.6:4567 X-Queue: 1.0 X-Queued: position=14; ID=6a074979f3201edbf323b6425fef4a53 HTTP/1.1 503 Queued Server: blah X-Queue: 1.0 X-Queued: position=1; length=4300; ETA=2100; ID=6a074979f3201edbf323b6425fef4a53 Retry-After: 30 <30 seconds later> GET /resource HTTP/1.1 User-Agent: blah X-Node: 13.4.5.6:4567 X-Queue: 1.0 X-Queued: position=1; ID=6a074979f3201edbf323b6425fef4a53 HTTP/1.1 200 OK Server: blah This sequence requires some explainations: the server is not replying with a "Connection: close" header, so according to regular HTTP/1.1 semantics, the connection is persistent. Therefore, after the delay imposed by the server (via the Retry-After header), the client can re-issue its request. Until it gets a 200 (or 206 for partial content) reply. If the connection between the server and the client is broken at this stage, the server will hold the slot for 300 seconds max the first time. The client can re-issue its request within the first 300 seconds, or the server will call back with a QUEUE request after 300 seconds (i.e. the implicit "lifetime" here is 300). To prevent abuse, servers MAY limit the amount of disconnections allowed within Sq, but it must allow at least 1 (one). As the slot moves towards the head of the queue (slot 1), the time between retries shrinks. The algorithm to compute the Retry-After is given by: x = 30 + 20 * (slot - 1) which is valid up to x = 20. After that, a constant retry timeout is used (e.g. 600 seconds). If all the slots before become cancelled, this will force the server to reserve the slot for that amount of time, so 600 seconds is a reasonable value. 5. Passive Queueing This section presents the passive queueing, i.e. only addresses clients that are unaware of PARQ (clients that do not send the X-Queue header, and which are incapable of handling the QUEUE callback). The principle of passive queueing is that the server remembers the IP address of the requesting servent and allocates a slot for it. This slot is kept as long as the servent retries within the next 300 seconds. Naturally, there is no Sq used with those clients. Even when the slot number is low enough to deserve an entry in the Sq, the server will act as if the slot was in Aq. The "lifetime" is implicitly set to 300 seconds. In order to avoid excessive requerying, the server will use the Retry-After: 250 header to indicate that it is useless to retry before 250 seconds (for instance). As the requests moves in the queue towards slot 1, this amount will decrease. It is suggested that the amount be initially set to 250 for slots up to 21 (included), and then to 30 + 20*(slot-1): 410 for slot=20, and 30 for slot=1. Since Retry-After is a standard HTTP header, all servents should already honour it correctly. If the client does not understand the header, it will requery at its normal rate (since it does not know about the queue). PARQ-compliant servers should not penalize the legacy servent for not honouring this header, other than banning the servent if he clearly hammers. This forces the server to hold slots for at most 300 seconds. In practice, servents requery every 60 seconds or so. 6. Discussion The main advantage of PARQ is that it provides a queueing system for modern servents whilst not completely preventing older servents from getting slots. Full deployment of PARQ will indeed take some time. Another important advantage is that it allows the download queue to be persisted. Even the Sq can be "persisted". This will prove most useful for non-firewalled clients, as they will get a callback from the server, possibly days later, when the server comes back online. There has to be some advantage to not being firewalled! It is also important to note that PARQ is only a slot reservation system. There is no correlation between a slot and a file. This means a client can request a file initially, and change its mind until the upload slot is allocated. The Remanence property of the queue can also be extended to overcome the lack of persistent connection support in HTTP/1.0 by reserving an upload slot for 300 seconds, to the same IP, same file! This can help servents behind a modem, that waited painfully to get an upload slot and once they got it, had their connection broken suddenly. The upload slots could even be "persisted", for PARQ-aware servents that are not firewalled: the server would then send back QUEUE requests to them, and they would get back their slot immediately. Because both the client and the server exchange version numbers via the X-Queue header, smooth upgrades will be possible: a server will always downgrade to a level acceptable by the client. And future versions of this specification will mandate that a client at level 1.2 be able to understand 1.1 and 1.0 replies from a server. The reason for using active retries within Sq, instead of merely relying on HTTP continuations (100 status) is that it allows propagation of the download mesh information, and also it allows the client to determine the requested range at the last minute. It even permits the client to change its mind and request a totally different file than it had initially done. 7. Backward Compatibility with Legacy Queueing BearShare and Shareaza support an incompatible queueing protocol, built before PARQ was launched (it's called "Active Queueing"). In order to allow for smooth transition to PARQ and at the same time not penalize PARQ-compliant clients that would connect to those legacy servers, any client advertising: X-Queue: 1.0 MUST also be prepared to honour the legacy queueing implementation. The legacy server will reply with: X-Queue: position=2,length=5,limit=4,pollMin=45,pollMax=120 It's easy to tell that it's a legacy servent, because PARQ servers will use the X-Queue header in replies to advertise the level used to reply. Therefore, any X-Queue header not starting with "digit.digit" must belong to the legacy implementation. In this header, the only fields of interest are: . position: this is the same as PARQ's. . length: this is the same as PARQ's. . pollMin: this is the same as PARQ's Retry-After header. . pollMax: this is the same as PARQ's "lifetime" field. Note that the separator used is ",", whereas PARQ uses ";". This means there can be multiple X-Queue headers in the reply, whereas PARQ's choice of ";" as the separator ensures the unicity of the X-Queued header in the reply. Like PARQ, those legacy servents require that the connection be maintained, i.e. they require HTTP/1.1 persistent connections (they only support some kind of Sq, in PARQ parlance). If the connection is dropped, the slot will be lost since those servers do not support Remanence. PARQ servers SHOULD support Active Queueing as well as PARQ (i.e. honour at least the X-Queue: 0.1 header and behave as in Active Queueing). 8. Conclusion Let's go back to the initial goals we had set and look how well we fulfill them: * Fairness: this is ensured by the FIFO nature of the queue and by the fact that we support both active and passive queueing. * Monitoring: low granularity when the request is far deep in the queue (Aq), the period of feedback increases as the request reaches Sq and moves to the first slots. Each client request also gives the instantaneous status (queue position, ETA). * Remanence: this is a property of the implementation, but PARQ makes it easy to support since it was designed with it in mind. * Legacy: this is assured by the passive queueing features of PARQ. A. Change History May 10th, 2003 - revision 1.0.a: * Changed X-Listen-IP headers into X-Node to be compliant with what BearShare is going to use (combination of X-Node and X-Features headers to obsolete headers like Chat: or Browse: in the requests). * Added the IP:port section to the QUEUE callback. Amazing that nobody had noticed that it was lacking! ________________________________________________________________________ Date: Tue, 13 May 2003 10:50:25 -0400 From: "Dave Nicponski" Subject: RE: PARQ updated Heyas Raphael! Thanks for this doc, sorry to take so long with my comments, etc. Sorry for any spelling errors, etc. Lotsa coffee =) [QUOTE] * Remanence: the queue must survive a servent shutdown, either on the client side or on the server side, provided the servent comes back "quickly". [/QUOTE] It appears from this text that this is for "short" client disconnects (<5 mins) or short/long server disconnects (any length). Although this may be intended for only 5 mins for server, contradicting info appears in the original post (and here (****), at bottom) confusing the server shutdown time across which queue persistence would be allowed. In any case, 1) Why "must [the queue] survive a servent shutdown" of more than 5 minutes? 2) Where did this requirement come from? 3) Why is it really desirable? From an end user standpoint? [QUOTE] Remanence allows the client or server to become unavailable for a short period of time (max. 5 minutes) and yet not perturb the queue. This property is valuable for modem users (this includes DSL users), which can experience a connection drop, and servent developers who can have their servent crash in the middle of an experiment. [/QUOTE] That is a nice feature of this scheme, one that is worthy of further exploration. However, I again state that this should probably for <5mins drop, long enough to reboot and continue. [QUOTE] PARQ maintains an arbitrary long queue (typically 5000 entries or more) which is split into two parts: [/QUOTE] A 5000 deep queue? What could possibly justify that? Do you really believe that a 5000 entry queue is useful? Without saving across launches >5mins? Really? No... It is as useful to a person entering that queue as a mirage is. Planning on saving that massive queue across launches >5 min? Even worse, see further down... [QUOTE] Aq. Asynchronous queue, the largest part[...] Sq. Synchronous queue, the smallest part.[...] [/QUOTE] Asynchronous - Lack of temporal concurrence; absence of synchronism Synchronous - Occurring or existing at the same time I would *highly* recommend using different terms, as those meanings do not pertain to the usage you have given them, and I know personally (from here) that using mis-defined terms "Asynchronous" & "Synchronous" will lead to bugs and problems. Trust me. =) [QUOTE] Optionally, non-firewalled clients that support PARQ can also support a new form of request that can be used by the server as a callback. It is similar to a GIV request sent by the server to the client when a PUSH is received. It is named "QUEUE" and will be detailed in section 4. [/QUOTE] I like this a lot. However, although this solves the "hold a connection open for queues" problem (among other things) please recall that queue slots are a shared, network-wide commodity. Like the now-famous and overused analogy, the "Tragedy of the commons" is waiting to happen here as well. Obviously, it benefits a user to be in as many queue slots as possible. However, these slots are actually consumed, preventing others from using them. Since there is no way to "force" a client asking for a queue slot to reveal how many *other* queue slots he is residing in, it is necessary to have a self-protecting mechanism. This protection (previously in active queuing) occurred by the nature of the system; to hold a queue slot requires maintaining an active TCP connection. Maintaining 5 queue slots required holding 5 TCP connections. Cost proportional to consumption == (somewhat) self controlling. With PARQ this useful "feature/liability" is gone. Instead, there is callback, which is admittedly *very* attractive. However, you lose the "cost proportional to consumption", preventing massive abuse. How can you prevent a client from taking 1000s and 1000s of queue slots now that they wouldn't pay any such price? If you don't how is this any better? (****) (Referenced text that may confuse persistance times, from above) [QUOTE] Another important advantage is that it allows the download queue to be persisted. Even the Sq can be "persisted". This will prove most useful for non-firewalled clients, as they will get a callback from the server, possibly days later, when the server comes back online. There has to be some advantage to not being firewalled! [/QUOTE] So, a server will persist its queue across launches >5 mins? To me, this is a *really* bad idea. If we had 1000 people in queue on Monday for file A, then go offline for a week, and 750 of those 1000 people finished their file from other sources, leaving 250 people still wanting the file from me. However, there are also an implicit group of new demand for the file as well. Coming back online, why should I try to contact those 1000 clients in my old queue? Each client knows (for itself) whether it still wants the file from that source, why not let them make the decision themselves? Then, only the 250 who still want a file from me would contact me, maybe get queued (again), etc... However, so would the "new" 250-500 people who want that file from me, and I am not wasting my time trying to send it to people who don't want it anymore. Again, I am drawn back to your stated goals for this queuing system: [QUOTE] 1) Fairness: this is ensured by the FIFO nature of the queue and by the fact that we support both active and passive queueing. 2) Monitoring: low granularity when the request is far deep in the queue (Aq), the period of feedback increases as the request reaches Sq and moves to the first slots. Each client request also gives the instantaneous status (queue position, ETA). 3) Remanence: this is a property of the implementation, but PARQ makes it easy to support since it was designed with it in mind. 4) Legacy: this is assured by the passive queueing features of PARQ. [/QUOTE] 1) Isn't a working, bug free queue system "FIFO" by definition? Why does it (the currently working queue) need to be re-written? Are you claiming that it isn't FIFO? 2) Current queue system allows monitoring of your progress through a queue. Why does it need to be re-written? Are you claiming it doesn't? True, it is server-optional to include this, and not all servers will show you your position. 3) Short term remanence (<5 mins) is great, but does not require a whole new queuing system. BearShare has "reserved slots" used when a client loses his connection, which accomplishes this without a new queue system. 4) Isn't the ultimate form of legacy support simply, "Don't create unnecessary upgrades that cause a perfectly valid system to become 'legacy' if it (new system) is not needed?" This is an artificial requirement, not a real one, as there is no "legacy" queue system to support if we don't create a second queue system. In addition, my own thoughts: 5) Why, oh why, would you want to go to 5,000 queue slots? Have you ever used IRC? Do you want Gnutella downloads to be like IRC? Please say no! 6) Is the 5,000 number for "user placebo" since "queued 4950/5000" looks better than "busy"? ********************************************************** 7) What is the problem you are trying to fix??? Please don't say "too many busys" or "not enough sources" as this does ***NOT*** solve that problem, nor does it even attempt to. http://www.bearshare.com/forum/showthread.php?s=&threadid=17301&highlight=vestibule Please see this link for a discussion (and my analysis) on "Queues, what are they good for (absolutely nothing!)", and my stated reasons for why queues do **not** help solve problems, any more than a bandaid covering a laceration does. True, it may prevent others from seeing my gash (aesthetics, like seeing queued 4958/5000, which is *really* a busy) but it doesn't actually HELP anything. ********************************************************** Any other thoughts? -dave- ________________________________________________________________________ Date: 13 May 2003 20:57:38 GMT From: Raphael_Manfredi@pobox.com Subject: Re: PARQ updated Quoting Dave Nicponski from ml.gnutella.dev-forum: :In any case, :1) Why "must [the queue] survive a servent shutdown" of more than 5 minutes? Servents do crash. On occasion due to bugs, or they are shutdown by their user. Sometimes, even the X server crashes, and that takes down the servent as well. :2) Where did this requirement come from? Myself. :3) Why is it really desirable? From an end user standpoint? You get the guarantee that if you were queued on a server, you can get back your entry some day. If you found a rare file, then this is a precious feature. :[QUOTE] :Remanence allows the client or server to become unavailable for a :short period of time (max. 5 minutes) and yet not perturb the queue. :This property is valuable for modem users (this includes DSL users), :which can experience a connection drop, and servent developers who can :have their servent crash in the middle of an experiment. :[/QUOTE] : :That is a nice feature of this scheme, one that is worthy of further :exploration. Thanks. You have a weird quoting style by the way. : :[QUOTE] :PARQ maintains an arbitrary long queue (typically 5000 entries or more) :which is split into two parts: :[/QUOTE] : :A 5000 deep queue? What could possibly justify that? :Do you really believe that a 5000 entry queue is useful? :Without saving across launches >5mins? Really? :No... : :It is as useful to a person entering that queue as a mirage is. 5000 is arbitrarily large. My PARQ queue is current about 1250 entries. When I launch GTKG, there is a grace period during which most entries time out, people not replying to QUEUE messages, etc... So those entries die. It's very rare to have a "live" queue of more than 100 entries (whereby all the 100 entries are regularily refreshed). :[QUOTE] :Aq. Asynchronous queue, the largest part[...] :Sq. Synchronous queue, the smallest part.[...] :[/QUOTE] : :Asynchronous - Lack of temporal concurrence; absence of synchronism :Synchronous - Occurring or existing at the same time Sorry for my poor choice, I'm not a native English speaker. Perhaps the words "passive queueing" and "active queueing" would be better. :[QUOTE] :Optionally, non-firewalled clients that support PARQ can also support a new :form of request that can be used by the server as a callback. It is similar :to a GIV request sent by the server to the client when a PUSH is received. :It is named "QUEUE" and will be detailed in section 4. :[/QUOTE] : :Since there is no way to "force" a :client asking for a queue slot to reveal how many *other* queue slots he is :residing in, it is necessary to have a self-protecting mechanism. This :protection (previously in active queuing) occurred by the nature of the system; :to hold a queue slot requires maintaining an active TCP connection. Maintaining :5 queue slots required holding 5 TCP connections. Cost proportional to :consumption == (somewhat) self controlling. With PARQ this useful :"feature/liability" is gone. Well, if one person queues to say 100 slots, its servent needs to maintain the slots by regularily contacting the server back. You have a short protection against your going down for a few minutes, but if you shutdown and come back a few hours later, your slot is lost anyway. So you have the incentive to stay online. Plus, with PFSP, you participate to the download mesh actively, since you will have a channel for propagating all the alternate locations (via the download/upload requests). That's also why PARQ queues need to be larger than active queues. There will be more slots reserved, but very few will reach slot #0 and get an upload slot. :Instead, there is callback, which is admittedly *very* attractive. :However, you lose the "cost proportional to consumption", preventing massive :abuse. How can you prevent a client from taking 1000s and 1000s of queue slots :now that they wouldn't pay any such price? If you don't how is this any better? Well, the PARQ queue has a shortcoming currently: one servent can queue several entries to the queue of one servent IN SEQUENCE. I don't want to limit the queueing to one entry per servent, due to the size of the queue. My idea is to make the queue full of holes: your first request would be queued at slot #45, say. Your second request would be at slot #145, the third at slot #245, etc... : :(****) (Referenced text that may confuse persistance times, from above) :[QUOTE] :Another important advantage is that it allows the download queue to :be persisted. Even the Sq can be "persisted". This will prove most :useful for non-firewalled clients, as they will get a callback from :the server, possibly days later, when the server comes back online. :There has to be some advantage to not being firewalled! :[/QUOTE] : :So, a server will persist its queue across launches >5 mins? :To me, this is a *really* bad idea. : :If we had 1000 people in queue on Monday for file A, then go offline for a week, :and 750 of those 1000 people finished their file from other sources, leaving 250 :people still wanting the file from me. :However, there are also an implicit group of new demand for the file as well. :Coming back online, why should I try to contact those 1000 clients in my old :queue? Because you don't know. The QUEUE callback is small enough to not become a resource hog. And if people have finished but wanted another file from you, they can always request that new file and keep their slot. : :Each client knows (for itself) whether it still wants the file from that source, :why not let them make the decision themselves? Then, only the 250 who still want :a file from me would contact me, maybe get queued (again), etc... However, so :would the "new" 250-500 people who want that file from me, and I am not wasting :my time trying to send it to people who don't want it anymore. You're forgetting about the dynamic IP problem. Perhaps the IP of the server changed, and they don't know where it is now. Whereas the IP of the client did not change yet, so the server can contact back. Or perhaps the server is firewalled, and can only make outgoing connections. :Again, I am drawn back to your stated goals for this queuing system: :[QUOTE] :1) Fairness: this is ensured by the FIFO nature of the queue and by the fact : that we support both active and passive queueing. :2) Monitoring: low granularity when the request is far deep in the queue (Aq), : the period of feedback increases as the request reaches Sq and moves to the : first slots. Each client request also gives the instantaneous status (queue : position, ETA). :3) Remanence: this is a property of the implementation, but PARQ makes it easy : to support since it was designed with it in mind. :4) Legacy: this is assured by the passive queueing features of PARQ. :[/QUOTE] : :1) Isn't a working, bug free queue system "FIFO" by definition? Why does it (the :currently working queue) need to be re-written? Are you claiming that it isn't :FIFO? Active queueing is FIFO only during the lifetime of your connection. My IP address changes every 24 hours, so if I don't get a chance to get an upload slot in 24 hours, then I loose my slot even though I waited for that time. Not with PARQ, because I will be able to reclaim my slot by recontacting the server once my IP has changed. :2) Current queue system allows monitoring of your progress through a queue. Why :does it need to be re-written? Are you claiming it doesn't? True, it is :server-optional to include this, and not all servers will show you your position. You have to remember that I wrote PARQ *without knowing about Active Queueing*. It's an independent invention, so of course there are overlapping features! I'm not claiming PARQ has original features. However, PARQ is consistent and offers more than "Active Queueing". :3) Short term remanence (<5 mins) is great, but does not require a whole new :queuing system. BearShare has "reserved slots" used when a client loses his :connection, which accomplishes this without a new queue system. Right. That's a good idea. I'm not claiming PARQ is the only system to offer short-term remanence. It just offers it. You seem to agree it's a good thing, so why not? :4) Isn't the ultimate form of legacy support simply, "Don't create unnecessary :upgrades that cause a perfectly valid system to become 'legacy' if it (new :system) is not needed?" This is an artificial requirement, not a real one, as :there is no "legacy" queue system to support if we don't create a second queue :system. By legacy here, I was referring to clients not understanding queuing at all. :In addition, my own thoughts: :5) Why, oh why, would you want to go to 5,000 queue slots? Have you ever used :IRC? Do you want Gnutella downloads to be like IRC? Please say no! What is the link with IRC? :6) Is the 5,000 number for "user placebo" since "queued 4950/5000" looks better :than "busy"? Well, chances are that a good part of the 4950 slots in front of you will die, letting you move forward faster than expected. : :********************************************************** :7) What is the problem you are trying to fix??? Please don't say "too many :busys" or "not enough sources" as this does ***NOT*** solve that problem, nor :does it even attempt to. :http://www.bearshare.com/forum/showthread.php?s=&threadid=17301&highlight=vestibule :Please see this link for a discussion (and my analysis) on "Queues, what are they :good for (absolutely nothing!)", and my stated reasons for why queues do **not** :help solve problems, any more than a bandaid covering a laceration does. True, :it may prevent others from seeing my gash (aesthetics, like seeing queued :4958/5000, which is *really* a busy) but it doesn't actually HELP anything. :********************************************************** Queues allow fairness. The first to request a file should be the first to get it. I saw too many times a newcommer arriving and "stealing" a slot that had become free in front of someone who had patiently been requesting a file once per minute for the last 10 hours. To conclude, PARQ works. GTKG has it, I can witness that it works. However, the current implementation needs tuning, because PARQ is more delicate than Active Queuing alone. For instance, when I launch GTKG with a ~1250 slot queue, it takes a good 20 minutes for the queue to purge itself and allow slot #1251 to become slot #1. During that time, GTKG allows no uploads to proceed. I'm not overly concerned about it though. This is the kind of thing that will improve over time. It's also the first implementation only, and "we must plan to throw it away" if we believe in Brooks. Raphael ________________________________________________________________________ >>>>> Here we had a stop. Three weeks later the discussion was startet again -Draketo <<<<< ________________________________________________________________________ Date: Thu, 05 Jun 2003 17:33:45 -0000 From: "mickish0" Subject: Unsolicited "QUEUE " messages BearShare sees agents connecting to it and sending messages that look like QUEUE ___190dc0f9b59f175759fc44e8b507c\r\n These messages are unsolicited and undesired. Please stop. Yes, I know these are PARQ messages, but BearShare does nothing to indicate PARQ compliance, so these messages are inappropriate. If you need a header to indicate PARQ compliance, please stop using the X-Queue header which indicates compliance with the much more widely adopted Queue standard. As you may recall, PARQ decided to step on the X-Queue header already in use by Active Queueing, either out of spite or out of an unwelcome attempt to interact/interfere with Active Queue clients: http://groups.yahoo.com/group/the_gdf/message/9464 Now that there are agents actually sending these messages, it is a real problem that must be dealt with maturely. (Alas...) P.S. If you insist on using X-Queue, then you might as well use nothing at all, since all major vendors already support Active Queueing, use X-Queue as the indicator, don't support PARQ, and are only inconvenienced by PARQ's current behavior. ________________________________________________________________________ Date: 5 Jun 2003 19:39:50 GMT From: Raphael_Manfredi@pobox.com Subject: Re: Unsolicited "QUEUE " messages Quoting mickish0 from ml.gnutella.dev-forum: :BearShare sees agents connecting to it and sending messages that look :like : : QUEUE ___190dc0f9b59f175759fc44e8b507c\r\n : :These messages are unsolicited and undesired. Please stop. [There's no need to obfuscate the above hex string. It's just a random ID] It's not gtk-gnutella's fault. It's someone who started to run a PARQ-compliant servent, then changed its IP address. You arrive and take his IP address, and get the PARQ messages. Those are only connection requests. It's like receiving a spurious GIV. Nothing more, nothing less. The amount of bandwidth consumed is very little. Just close the connection and be happy. :Yes, I know these are PARQ messages, but BearShare does nothing to :indicate PARQ compliance, so these messages are inappropriate. Well, no. If you ignore them, gtk-gnutella will stop sending them after two times (for any given ID that was queued though). :If you need a header to indicate PARQ compliance, please stop using :the X-Queue header which indicates compliance with the much more :widely adopted Queue standard. Why are you so hostile? It's not like PARQ was not discussed on the GDF, the specs are public and were reviewed. Everyone knew it will become a reality one day. :As you may recall, PARQ decided to step on the X-Queue header already :in use by Active Queueing, either out of spite or out of an unwelcome :attempt to interact/interfere with Active Queue clients: : :http://groups.yahoo.com/group/the_gdf/message/9464 Yes. And PARQ plays very nice with active queueing by defaulting to it for lesser (sic!) servents that do not yet understand it. :Now that there are agents actually sending these messages, it is a :real problem that must be dealt with maturely. (Alas...) I don't see the problem you're having with X-Queue. I suggest you re-read the PARQ specs calmly, and see that PARQ is right to use X-Queue: 1.0 in its requests, since it supports both 0.1 and 1.0. Now, on the reply, yes, it steps on X-Queue's toes, but only if the remote host advertised 1.0 or higher. If the remote advertised 0.1, it plays nice and downgrades to Active Queuing. :P.S. If you insist on using X-Queue, then you might as well use :nothing at all, since all major vendors already support Active :Queueing, use X-Queue as the indicator, don't support PARQ, and are :only inconvenienced by PARQ's current behavior. What kind of inconvenience is that? I feel like you're highly irritated. I can't understand why. If you don't like PARQ, don't implement it. But PARQ works so well that I recommend you support it. Raphael ________________________________________________________________________ Date: Thu, 05 Jun 2003 21:40:58 -0000 From: "mickish0" Subject: Re: Unsolicited "QUEUE " messages It's not gtk-gnutella's fault. It's someone who started to run a PARQ-compliant servent, then changed its IP address. You arrive and take his IP address, and get the PARQ messages. No, this is not the case. My IP address at work is not changing, yet I get these messages. Well, no. If you ignore them, gtk-gnutella will stop sending them after two times (for any given ID that was queued though). OK, thanks. Why are you so hostile? Because you deliberately used a header already in use for another purpose. It's not like PARQ was not discussed on the GDF, the specs are public and were reviewed. On the GDF, FreePeers objected to your proposed use of X-Queue, but you apparently decided to use it anyway. ________________________________________________________________________ Date: Thu, 05 Jun 2003 22:35:19 -0000 From: "Raphael Manfredi" Subject: Re: Unsolicited "QUEUE " messages --- In the_gdf@yahoogroups.com, "mickish0" wrote: It's not gtk-gnutella's fault. It's someone who started to run a PARQ-compliant servent, then changed its IP address. You arrive and take his IP address, and get the PARQ messages. No, this is not the case. My IP address at work is not changing, yet I get these messages. Then I don't know how you can receive them. PARQ can't send out QUEUE messages unless it sees an X-Node: header in the HTTP requests to indicate the IP:port of the host, and the requesting servent advertised support for PARQ, of course. Wait... No, there's a bug in GTKG's implementation. We peruse X-Node even if the remote servent does not advertise X-Queue: 1.0. Thanks! (You must have been sending out X-Node: headers in your HTTP requests) Why are you so hostile? Because you deliberately used a header already in use for another purpose. Uh? I defined "X-Queue: 1.0" on the request side. This is perfectly valid, as it is an upward compatible version! On the response side, yes, I use X-Queue differently, but in a totally backward compatible way (i.e. it's either used as legacy queuing dictates, or it's a PARQ version number if the requesting servent advertised PARQ). Again, I see nothing wrong here. Quite the contrary. I think the fact you were seeing QUEUE message was due to the aforementionned bug. Sorry. Raphael ________________________________________________________________________ Date: Thu, 05 Jun 2003 22:45:01 -0000 From: "Vinnie" Subject: Re: Unsolicited "QUEUE " messages --- In the_gdf@yahoogroups.com, Raphael_Manfredi@p... wrote: Why are you so hostile? It's not like PARQ was not discussed on the GDF, the specs are public and were reviewed. Everyone knew it will become a reality one day. No, we "knew" it would become a reality because of your stubbornness towards including it despite its (near) uselessness. In fact, the whole concept of remote queuing is flawed and we should get rid of it. The problem is that if only one vendor supports it, it gives upload slots to that vendor only, causing disparate sharing. Remote queuing only pushes the "busy" problem to the end of the queue, rather than at the last upload slot. It is merely a placebo that makes users feel comfortable that they are at least waiting in line. eMule is a perfect example of how miserable queuing fails. In fact, GTK-Gnutella cribs a page from eMule's less than stellar playbook by advocating VERY LARGE queue sizes (5000? madness?). For a more detailed explanation of why queueing is just a waste of programmer time and user resource, I will refer you to Dave. ________________________________________________________________________ Date: Thu, 05 Jun 2003 22:46:40 -0000 From: "Vinnie" Subject: Re: Unsolicited "QUEUE " messages --- In the_gdf@yahoogroups.com, "Raphael Manfredi" wrote: I think the fact you were seeing QUEUE message was due to the aforementionned bug. Sorry. We must eliminate PARQ, or specifically, the part where it connects back to you, IMMEDIATELY! There is currently a very big problem with uploads, in that servers are getting overwhelmed with outgoing bandwidth limits trying to respond to so many incoming requests (even if it is just to Busy them). You MUST AVOID making this problem worse by having the upload side periodically contact the downloader (wasting his bandwidth and yours) unsolicited. The "passive" queuing with periodic re-contacting is absolutely a BAD IDEA. Please rectify. ________________________________________________________________________ Date: 5 Jun 2003 22:54:28 GMT From: Raphael_Manfredi@pobox.com Subject: Re: Unsolicited "QUEUE " messages Quoting Vinnie from ml.gnutella.dev-forum: :We must eliminate PARQ, or specifically, the part where it connects :back to you, IMMEDIATELY! No. I don't have to take orders from you. Sorry. :There is currently a very big problem with uploads, in that servers :are getting overwhelmed with outgoing bandwidth limits trying to :respond to so many incoming requests (even if it is just to Busy :them). So implement PARQ and support Retry-After. You'll get far less requests. :You MUST AVOID making this problem worse by having the upload side :periodically contact the downloader (wasting his bandwidth and yours) :unsolicited. The "passive" queuing with periodic re-contacting is :absolutely a BAD IDEA. I don't see it that way. PARQ will only attempt to recontact two times, and, if ignored, will stop bugging the host for that queued entry. The message is SO SMALL that it is far less work than rejecting an incoming Gnutella connection. So please, give me a good reason. Just because you disagree does not mean you're right. :Please rectify. I don't see anything to rectify yet, sorry. You'll have to convince me, not give me blunt orders. Raphael ________________________________________________________________________ Date: Thu, 05 Jun 2003 22:58:49 -0000 From: "Vinnie" Subject: Re: Unsolicited "QUEUE " messages --- In the_gdf@yahoogroups.com, Raphael_Manfredi@p... wrote: I don't see anything to rectify yet, sorry. You'll have to convince me, not give me blunt orders. It can be demonstrated that remote queuing does nothing to improve the likelihood of downloading a file. It can also be shown that remote queues do not reduce the frequency of busy signals. Dave's original argument against remote queues: ----------------------------------------------- http://www.bearshare.com/forum/showthread.php?threadid=17301 The message is towards the bottom. This is a copy of his post: --------------------------- quote: ---------------------------------------------------------------------- ---------- Originally posted by ThomasWalton How long you can stay online is a big factor for these large files with queues. The more limited the sources the more value I see for queues to exist. Before queues I would never attempt to download a single sourced very large 1GB+ size file. And the large 400MB+ files with multi sources have a very high rate of success with queues. Many queues are quick for these files as so many clients lose connectivity (or are swarming) and I'm quite happy to be next in line to start my download. ---------------------------------------------------------------------- ---------- Also, remember this: Since very few queue-compatible vendors exist, and any non-queue capable host who requests a file from a queue- capable one will get a BUSY. Result: Once a single downloader is occupying a queue slot, and if there are enough file requests to always keep at least a single downloader in queue, then ONLY those few (2) vendors which support queueing will EVER be able to successfully download. No other vendors will be able to transfer until all queue-enabled vendors are satisfied. This is a very important observation to understand the real reason everything seems better now. No Morpheus client will Ever be able to get a file from a queue-enabled source until all BearShare/Shareaza client requests have been satisfied (made active). If there is even a single queues BearShare/Shareaza requestor, all other clients are put on hold until this VIP client's request has been satisfied. So: Right now, you see a huge improvement. However, as more and more vendors support queuing, you will see the same type of compitition for queue slots as there used to be for download slots. Here was the analogy I used to play Devil's advocate for queues: Picture a street, Main Street, with 5 clubs on it. There are several people who want to get into these clubs, but they can't satisfy the number of requests to enter the club. Hence, there are some people inside, and several people waiting near the front door. Some of those waiting people are well-behaved, and return every minute or so to see if someone left. Others are not so well behaved. They try every 10 seconds, or so. Not so often that I have them arrested for harrasment (blocked), but just on the other side of 'hammering' behavior. So, for example, there are 10 "waiters". The good ones re-check every minute, so in 10 minutes time, any given "Good Waiter" will check 10 times. The "Evil Waiter" will check every 10 seconds, so in 10 minutes time he will have made 60 requests. Since there is little or no correlation between these requests, and the availability of a free space (someone left the club) it is essentially a random game, first person to make the request once a condition is met wins. Since 'Evil Waiter" made 6 times as many requests, we would expect him to be 6 times as likely to get the next available opening. Obviously, this is not the behavior we want to encourage. So, introduce Queueing. Now, right outside the Front door, we add a vestibule. We require that anyone in the vestibule be well-behaved, be a VIP card holder (they must support queuing) and wait their turn to go through the front door. This is great right now, since all Bear's are VIPs (support queuing) you will always be able to slip into the vestibule if there is an open space in the vestibule. As more clients get VIP cards (support queuing) the situation changes fundamentally. Now, all clients inside the vestibule are well-behaved. But: What about right outside the front door to THAT vestibule? Who gets the first open queue/vestibule slot when one becomes available? Well, the first person who reqests it, right? So really, all we have done with Queuing (when more clients support it) is move the congestion (and unfair behavior) from the front door of the club, to the front door of the vestibule. The overall situation is unchanged: Before, p = person: [Club] p, p, p, p, [Front Door]pppppppppppp Now, p = person: [Club] p, p, p, p, [Vestibule] p, p, p, p, [Front Door]pppppppppppp In each case, the REAL problem is caused by the [Front Door]pppppppp congestion. This causes the behavior of "hammering but not quite" to be "desirable" (as far as having the best chance to grab a file), and leads to the now-infamous 'Tragedy of the Commons' scenario. The underlying problem of congestion/unfair behavior has not been solved. Sure it SEEMS that way now, because of the effect of requiring VIP cards to get into the vestibule, but once other clients support this we are no better off. This can be made even more apparent by unifying queue slots with upload slots. Instead of Active/Queued, pretend they are Fast/Slow (Fast = active, Slow = queued). If nothing goes wrong, then all Slow will eventually become Fast, and complete. So therefore, queuing has essentially forced an increase of the number of Upload slots, without increasing upload capacity. If people couldn't handle the rate of file transfer requests (as evidenced by the massive number of BUSYs) with n upload slots, what good will changing n to n+m have? Recall we havent changed the RATE at which we handle these transfers. We have simply allowed more of them to start at once. Now, there are other factors to consider, such as user oppinion (Queued 11/12) looks better than 'Busy', even if there was a chance for you to slip in to the Busy slot as soon as it opened, faster than waiting for 11 transfers to complete. So I hope this gives you all something to think about. quote: ---------------------------------------------------------------------- ---------- It would still be nice to see some tweaks to queues to allow jumping into your open slot and to make the wait delay on the server side so responses sent to the client are either wait some more or start now. ---------------------------------------------------------------------- ---------- You mean to speed up the moment from Queue slot 1 to active transfer? At most, this should be 30 seconds or so currently. quote: ---------------------------------------------------------------------- ---------- With small files swarming with many sources upload bandwidth has no way to pipeline and if you watch the bandwidth for single uploads you see blips of activity followed by long delays, but not so with large files are the swarmed segment is much larger. Maybe multi-sources can do some more overlapping (like at end of transfer) by using larger request sizes and quickly dropping the slow transfers in favor of the faster transfers (again for small < 5MB? files.) ---------------------------------------------------------------------- ---------- This happens already (If I understand you message correctly, which I may not) Hope this helps! -dave- __________________ Defender of the free world since 2002! -Omnis tuus castra sunt inesse nos- .........<== Sam was the 1st to translate this! Information truly wants to be worthless! ...with Liberty and Justice for some... ________________________________________________________________________ Date: 5 Jun 2003 23:09:02 GMT From: Raphael_Manfredi@pobox.com Subject: Re: Unsolicited "QUEUE " messages Quoting Vinnie from ml.gnutella.dev-forum: :--- In the_gdf@yahoogroups.com, Raphael_Manfredi@p... wrote: :> Why are you so hostile? It's not like PARQ was not discussed on the :> GDF, the specs are public and were reviewed. Everyone knew it will :> become a reality one day. : :No, we "knew" it would become a reality because of your stubbornness :towards including it despite its (near) uselessness. When I introduced compression, it was believed to be as useless. :In fact, the whole concept of remote queuing is flawed and we should :get rid of it. The problem is that if only one vendor supports it, it :gives upload slots to that vendor only, causing disparate sharing. Right. It is true that the fact that you do not support PARQ gives a small advantage to servents that support it. But it's not my fault. :Remote queuing only pushes the "busy" problem to the end of the :queue, rather than at the last upload slot. It is merely a placebo :that makes users feel comfortable that they are at least waiting in :line. No, it is a fair queueing system. It avoid having people hammering in order to get the chance to grab an upload slot that was just freed. Quite the contrary, if you don't abide by the rules edicted by the server, via the Retry-After header, you'll be punished. :eMule is a perfect example of how miserable queuing fails. In fact, :GTK-Gnutella cribs a page from eMule's less than stellar playbook by :advocating VERY LARGE queue sizes (5000? madness?). I take your word for it. What is the problem exactly? :For a more detailed explanation of why queueing is just a waste of :programmer time and user resource, I will refer you to Dave. Sorry, I disagree with Dave. Despite my node changing IP addresses every 24 hours, I've been able to guarantee other PARQ-compliant hosts their place in the queue, so they did not have to locate my node again. This is thanks to the QUEUE feature you loathe so much. Also, after a shutdown this morning, I was able to let other servents resume their uploads that were suddenly aborted. Again, this is a PARQ feature, and no, it was not even for PARQ-enabled servents. Simply their slots were reserved. And the large queue size (we retained 4000 per queue in our implementation) is only for recording purposes. In practice, there are only a few dozens servents waiting, either actively or passively. PARQ is completely transparent. If you don't like it, so be it. But don't try to deprive GTKG users and others from a very useful feature. Sure, there are some bugs that can cause small grief, but give it time to stabilize. PARQ is a delicate piece that requires some tuning. Raphael ________________________________________________________________________ Date: 5 Jun 2003 23:17:23 GMT From: Raphael_Manfredi@pobox.com Subject: Re: Unsolicited "QUEUE " messages [It's Dave's posting as cut-n-pasted by Vinnie that is quoted here] :Also, remember this: Since very few queue-compatible vendors exist, :and any non-queue capable host who requests a file from a queue- :capable one will get a BUSY. : :Result: Once a single downloader is occupying a queue slot, and if :there are enough file requests to always keep at least a single :downloader in queue, then ONLY those few (2) vendors which support :queueing will EVER be able to successfully download. No other vendors :will be able to transfer until all queue-enabled vendors are :satisfied. This is a very important observation to understand the :real reason everything seems better now. No Morpheus client will Ever :be able to get a file from a queue-enabled source until all :BearShare/Shareaza client requests have been satisfied (made active). :If there is even a single queues BearShare/Shareaza requestor, all :other clients are put on hold until this VIP client's request has :been satisfied. This is the unfortunate situation created by Active Queueing, yes. I used this very same argument against Active Queueing when it was published, but was not heard. But PARQ is really different, in that it allows passive queueing. Even if you don't understand queuing on the client side, you'll get queued nonetheless, and in a fair manner. Provided you abide by HTTP rules, process the Retry-After header correctly, and don't change your IP address. This is all what is required! : :So, introduce Queueing. Now, right outside the Front door, we add a :vestibule. We require that anyone in the vestibule be well-behaved, :be a VIP card holder (they must support queuing) and wait their turn :to go through the front door. : :This is great right now, since all Bear's are VIPs (support queuing) :you will always be able to slip into the vestibule if there is an :open space in the vestibule. As more clients get VIP cards (support :queuing) the situation changes fundamentally. Now, all clients inside :the vestibule are well-behaved. : :But: What about right outside the front door to THAT vestibule? Who :gets the first open queue/vestibule slot when one becomes available? :Well, the first person who reqests it, right? : :So really, all we have done with Queuing (when more clients support :it) is move the congestion (and unfair behavior) from the front door :of the club, to the front door of the vestibule. The overall :situation is unchanged: This is why PARQ defines arbitrarily large queues. In effect, it makes the Vestibule so big that in practice, it never fills up. :Now, there are other factors to consider, such as user oppinion :(Queued 11/12) looks better than 'Busy', even if there was a chance :for you to slip in to the Busy slot as soon as it opened, faster than :waiting for 11 transfers to complete. Well, the only advantage here is that, hopefully, if you're not a brain dead servent, you'll set up a larger retry delay for a queue entry. So the requester will not hammer you once every minute but probably once every 10 minutes. You've divided the bandwidth necessary to reply to those requests by an order of magnitude. Raphael ________________________________________________________________________ Date: Thu, 05 Jun 2003 23:59:29 -0000 From: "Vinnie" Subject: Re: Unsolicited "QUEUE " messages --- In the_gdf@yahoogroups.com, Raphael_Manfredi@p... wrote: I used this very same argument against Active Queueing when it was published, but was not heard. That doesn't mean that you weren't right, or that you should propagate the turd by layering more crap on top of an already-faulty system. But PARQ is really different, in that it allows passive queueing. It cannot be proven that this reduces busy signals. It only pushes the problem to the end of the queue, instead of the end of the active upload slots (the "vestibule problem" according to Dave). This is why PARQ defines arbitrarily large queues. In effect, it makes the Vestibule so big that in practice, it never fills up. I've heard bigger loads, but this one is pretty large. You are kidding of course, right? ________________________________________________________________________ Date: Fri, 06 Jun 2003 15:16:19 -0000 From: "mickish0" Subject: Re: Unsolicited "QUEUE " messages Wait... No, there's a bug in GTKG's implementation. We peruse X-Node even if the remote servent does not advertise X-Queue: 1.0. Thanks! Ah, I hoped something like that was the case, but my pessimism made me think the observed behavior was deliberate. I apologize for assuming the worst. ________________________________________________________________________ Date: Mon, 9 Jun 2003 11:30:07 +0200 From: Jann Röder Subject: AW: Re: Unsolicited "QUEUE " messages Hi, I'd like to contribute my opinion on PARQ. I think it does something to improve downloads. You're right, the current (active) queuing system only pushes the problem (lack of slots) to the end of the queue. a passive queue would indeed reduce busy signals and reduce connection overhead. For maintaining an active queue slot an active connection is required and you have to re-ask every 90 seconds or whatever. With PARQ the servant can tell you to ask again in several hours if the queue is very long. In my eyes this reduces network traffic a lot. Also without queues and with the current system it is more or less coincidence whether you get a queue/upload slot or not. With PARQ you will be rewarded for waiting longer. But for this to work a client which implements PARQ should also rotate upload slots, so that you have a chance to reach the top of the queue. The current queuing system is not suitable for large files. If you have many large files, your upload slots will fill up and the user who has had enough luck to be the first to ask for a slot can use his slot until he has finished downloading. However for large files and most connections this will take several hours. Also the idea of having a queue that survives a disconnect is a good idea. 24h hour - disconnects are very common. And for downloading large files, you have to wait long, that's a fact. If you spend this time asking every 60 seconds for an upload / queue slot or if you spend the time waiting in a PARQ queue asking every 60 minutes for a slot update doesn't matter. Of course PARQ isn't some magic stuff that doubles upload capacity of the network, but it adds more fairness for uploads. A problem is, that you might have to wait really long for small files. A solution for that problem is having two queues. One for large and one for small files. Jann -- Jann Roeder ICQ: #29794099 PGP key ID: 0xC4A1DB89 ________________________________________________________________________ Date: 9 Jun 2003 09:38:00 GMT From: Raphael_Manfredi@pobox.com Subject: Re: AW: Re: Unsolicited "QUEUE " messages Quoting from ml.gnutella.dev-forum: :Of course PARQ isn't some magic stuff that doubles upload capacity of the :network, but it adds more fairness for uploads. Right. Also note that just because you're passively queued does not mean you don't have to periodically refresh your entry. If you stop doing that within the defined lifetime of the entry, the server sends you a QUEUE message (if you advertised PARQ when requesting). Failure to respond means your entry is flagged as "dead" and will be reclaimed in a FIFO order when the queue is full and we need some room. :A problem is, that you might have to wait really long for small files. :A solution for that problem is having two queues. One for large and one :for small files. GTKG's implementation of PARQ defines as many queues as there are upload slots. For instance, if you have 3 upload slots, you'll have 3 queues. One for large files, one for medium-sized, and one for small. Raphael ________________________________________________________________________ Date: Mon, 9 Jun 2003 11:16:23 -0400 From: "Dave Nicponski" Subject: RE: Re: Unsolicited "QUEUE " messages [quote] Of course PARQ isn't some magic stuff that doubles upload capacity of the network, but it adds more fairness for uploads. [/quote] Exactly my point... What, exactly, is this "fairness"? Can you give me a good mechanism for measuring/quantifying it? If not, this point isn't really valid, as it results in a "user-placebo" which, admitedly, may be better than nothing. However, be very careful when making claims like "Queues lead to fairness" and the like... Without being able to quantify this you will have a hard time demonstrating anything more than placebo effect. [quote] A problem is, that you might have to wait really long for small files. A solution for that problem is having two queues. One for large and one for small files. [/quote] See, this just illustrates my point that queues don't really "SOLVE" any problem! =) Its all mental! =) Lets examine something here... DisneyLand, say, since it was mentioned in-office on Friday as an example of "why queuing works"... Tons of (long) queues there. It is my belief that they work *only* because a ***Very High Penalty*** can be imposed for 'misbehavior' (leaving the line results in an hour or more of lost time) It is really a benefit/punishment system, right? IF: You stand quietly in line for 2 hours, and don't disturb others or make a scene, i will let you ride a ride. IF: You wander out of line, looking for a shorter line or differant ride, then I can (and will) remove you from the line you were residing in. Therefore, the *maximum resource consumption PER PERSON* (number of line spots being occupied) can be easily controlled. These are not the case here. I can easily take up 19 queue spots in 19 queues, without any penalty to me. I can grab a 20th spot with still no penalty. With PARQ, i could (conceivably) take up 1000 slots... Where is the benefit here? Where does the advantage come in? What, exactly, is being solved/accomplished by this queue, besides arbitrarily adding to the expected file completion time? Noone has yet given a good, quantifiable answer to this question; just stuff like "It seems more fair", or "Queues make downloads better" or other such propaganda-ish statements, without anything to back it up. Just my $0.02. -dave- **Give me a QUEUE slot today, and I'll gladly repay you on Tuesday** ________________________________________________________________________ Date: 9 Jun 2003 15:40:33 GMT From: Raphael_Manfredi@pobox.com Subject: Re: Unsolicited "QUEUE " messages Quoting Dave Nicponski from ml.gnutella.dev-forum: :These are not the case here. I can easily take up 19 queue spots in 19 queues, :without any penalty to me. I can grab a 20th spot with still no penalty. With :PARQ, i could (conceivably) take up 1000 slots... Where is the benefit here? I don't understand what you mean. If you grab a slot, you have to maintain it by re-requesting within the specified lifetime. Or you run a chance to loose it. If you reserve 1000 slots in 1000 queues and don't refresh them, they'll die when they expire and some room is needed in the queue. So you will have accomplished nothing, and penalized noone because of that. You will have just lost bandwidth requesting them in the first place. The queue is large, but if you don't use your slots, they'll be reclaimed. If you use them however, then what's the problem? To request 1000 slots, you will need to allocate the RAM necessary, and make the periodic requests. There is a limit to the number of requests a servent can make per second, due to bandwidth constraints. Raphael ________________________________________________________________________ ________________________________________________________________________ Message: 4 Date: Mon, 9 Jun 2003 11:56:32 -0400 From: "Dave Nicponski" Subject: RE: Re: Unsolicited "QUEUE " messages The point, that you are missing, is this: A queue in the physical world works well because we can use it to force a given behavior. I don't believe that this is possible with queues online like this. How can we force good behavior to other queue slots? Doesn't gobbling up as many queue slots as possible now "make the most sense" as far as user preformance goes? How is this fundamentally differant than "Life Without Queues(tm)"? Again, the fundamental questions are these; and we cannot progress until they are answered: (1) WHAT, EXACTLY, are you trying to accomplish with a queuing system? (2) HOW, EXACTLY, is the queuing systems today (active/PARQ/whatever) accomplishing that? (3) WHAT, EXACTLY, is the benefit of queuing system? Again, these tend to be answered as if queues were "the natural state of things". Why? Remember everyone, Physical World != Digital World!! Even though General Public (in real world) is happy to be herded like cattle, doesn't mean that it is appropriate or even desirable to drag this "functionality" into Gnutella... I would like to see some kinda justification for all this work done with queues. QRP, for instance, inherantly benefits people, and therefore development work could be justifiable. -dave- -----Original Message----- From: Raphael_Manfredi@pobox.com [mailto:Raphael_Manfredi@pobox.com] Sent: Monday, June 09, 2003 11:41 AM To: the_gdf@yahoogroups.com Subject: [the_gdf] Re: Unsolicited "QUEUE " messages Quoting Dave Nicponski from ml.gnutella.dev-forum: :These are not the case here. I can easily take up 19 queue spots in 19 queues, :without any penalty to me. I can grab a 20th spot with still no penalty. With :PARQ, i could (conceivably) take up 1000 slots... Where is the benefit here? I don't understand what you mean. If you grab a slot, you have to maintain it by re-requesting within the specified lifetime. Or you run a chance to loose it. If you reserve 1000 slots in 1000 queues and don't refresh them, they'll die when they expire and some room is needed in the queue. So you will have accomplished nothing, and penalized noone because of that. You will have just lost bandwidth requesting them in the first place. The queue is large, but if you don't use your slots, they'll be reclaimed. If you use them however, then what's the problem? To request 1000 slots, you will need to allocate the RAM necessary, and make the periodic requests. There is a limit to the number of requests a servent can make per second, due to bandwidth constraints. Raphael Yahoo! Groups Sponsor To unsubscribe from this group, send an email to: the_gdf-unsubscribe@egroups.com Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service. ________________________________________________________________________ ________________________________________________________________________ Message: 5 Date: 9 Jun 2003 16:03:50 GMT From: Raphael_Manfredi@pobox.com Subject: Re: Unsolicited "QUEUE " messages Quoting Dave Nicponski from ml.gnutella.dev-forum: :Again, the fundamental questions are these; and we cannot progress until :they are answered: :(1) WHAT, EXACTLY, are you trying to accomplish with a queuing system? The goals are stated in the PARQ specs. But generally speaking, we want to avoid hosts hammering back every 60 seconds or so to get a slot, and we don't want to give a slot by chance to someone just requesting now, whereas someone has been patiently requesting the file for days, but just happens to not be requesting right now. This is the fundamental goal of any queueing system. PARQ has others, but the above one is present, and is called "Fairness". :(2) HOW, EXACTLY, is the queuing systems today (active/PARQ/whatever) :accomplishing that? As far as the main goal stated above is concerned, both Active Queuing and PARQ satisfy that goal. Of course, PARQ has other goals, in particular "Legacy" and "Remanence". :(3) WHAT, EXACTLY, is the benefit of queuing system? Benefits for the server: less hammering, since retry time can be controlled. Benefits for the client: once in line, one know that there is no interest to hammer and retrying at the times specified by the server will allow correct scheduling of the request when the time comes. Raphael ________________________________________________________________________ ________________________________________________________________________ Message: 6 Date: Mon, 9 Jun 2003 18:18:35 +0200 From: Jann Röder Subject: AW: Re: Unsolicited "QUEUE " messages [quote] Of course PARQ isn't some magic stuff that doubles upload capacity of the network, but it adds more fairness for uploads. [/quote] However, be very careful when making claims like "Queues lead to fairness" and the like... Without being able to quantify this you will have a hard time demonstrating anything more than placebo effect. Without queues you might start downloading if you're lucky and get an upload slot. If you're not so lucky you end up asking over and over again without success. With PARQ you will start downloading if you just wait long enough. Of course this requires users to stay online for a large amount of time. But for downloading large files this is required anyway. Because I tend to stay online really long, it seems better to me to know that I will start downloading if I just wait long enough, rather than knowing, that I might start downloading if I eventually find a slot. See, this just illustrates my point that queues don't really "SOLVE" any problem! =) Its all mental! =) I think queues help to manage downloading of large files. A year or so ago, when there where no queues I used gnutella to download small mp3 files. The queue-less system worked those days, because mp3s didn't take that long to transfer so upload slots where freed quite often. Now that I download large files, the situation is different. If an upload slot is taken by a large-file upload it will take really long until the slot is freed again. I think we need queues to ensure that you can download large files. And I think it is better to make it in an organized manner rather than leaving it up to coincidence whether you can download or not. Lets examine something here... DisneyLand, say, since it was mentioned in-office on Friday as an example of "why queuing works"... Tons of (long) queues there. It is my belief that they work *only* because a ***Very High Penalty*** can be imposed for 'misbehavior' (leaving the line results in an hour or more of lost time) It is really a benefit/punishment system, right? IF: You stand quietly in line for 2 hours, and don't disturb others or make a scene, i will let you ride a ride. IF: You wander out of line, looking for a shorter line or differant ride, then I can (and will) remove you from the line you were residing in. Therefore, the *maximum resource consumption PER PERSON* (number of line spots being occupied) can be easily controlled. These are not the case here. I can easily take up 19 queue spots in 19 queues, without any penalty to me. I can grab a 20th spot with still no penalty. With PARQ, i could (conceivably) take up 1000 slots... Where is the benefit here? Where does the advantage come in? What, exactly, is being solved/accomplished by this queue, besides arbitrarily adding to the expected file completion time? The advantage is that if you have waited long enough you can start riding all the time. You might have to wait longer at first because there are many people in many queues, but after some time you can start the first ride and after you have finished that ride you can go on to the next ride almost immediately. Since having a computer waiting for something is by far not as annyoing as waiting in queue in Disneyland, I don't see a problem with that. Jann ________________________________________________________________________ Date: Mon, 09 Jun 2003 16:54:34 -0000 From: "dague12" Subject: Re: Unsolicited "QUEUE " messages --- In the_gdf@yahoogroups.com, "Dave Nicponski" wrote: Exactly my point... What, exactly, is this "fairness"? Can you give me a good mechanism for measuring/quantifying it? If not, this point isn't really valid, as it results in a "user-placebo" which, admitedly, may be better than nothing. However, be very careful when making claims like "Queues lead to fairness" and the like... Without being able to quantify this you will have a hard time demonstrating anything more than placebo effect. Queue gives fairness in the sense that everyone is going to have to wait a similar time to get the upload slot. Without queue you have an anarchy where anybody can get the slot, you might have people that get it in 1 minute, as well as people that is never able to get in. Lets examine something here... DisneyLand, say, since it was mentioned in-office on Friday as an example of "why queuing works"... Tons of (long) queues there. It is my belief that they work *only* because a ***Very High Penalty*** can be imposed for 'misbehavior' (leaving the line results in an hour or more of lost time) It is really a benefit/punishment system, right? Hmm, I wasn't pro PARQ much, but this example now convinces me that PARQ is good. Have you seen the FastPass they use, well that's a form of passive queue that you don't have to wait in line, but your line place is being kept. At the end it allows everyone to wait the same amount of time to get in. Sorry, I wrote this kind of in a hurry. ________________________________________________________________________ ________________________________________________________________________ Message: 9 Date: Mon, 9 Jun 2003 14:16:42 -0400 From: "Dave Nicponski" Subject: RE: Re: Unsolicited "QUEUE " messages Well, since many admittedly intellegent people see this exactly the opposite as i do, perhaps I am mistaken. For the remainder of this, PRETEND that I completely agree with all your judgements... Even if that were so, that i were completely wrong about this all, let me ask you all this: 1) Do you want a system where the wait time for files is expected to be equally horrible and lengthy, or one where half your files finish rapidly and the other half take awhile? Is the one really that much better than the other? I like having a decent chance for some files to finish rapidly. I don't like knowing ahead of time that all (or most) files have a known multi-hour wait time. DisneyLand approach has no appeal, to me. Ontario Place (where some rides had LOOOONG lines and others had none) was MUCH more appealing to me (at least, back when I went there) than one where all rides have long lines. Then I can skip the LOOOOnger ones and go to the rapid, fast pace ones... Just a thought... 2) Lets consider from average user, not even we the developers... Is a system where all (or most) files have much more lengthy wait times (of hours+), rather than having a decent chance for half files to finish FAST and other half to finish Slooooowly really that desireable??? Seriously consider this long and hard, before simply assuming it to be the case... =) At least for (2), I PERSONALLY don't think it is more desireable. You all are, of course, welcome to disagree with me. =) Would anyone disagree that file transfer times (For not MASSIVELY rare files) assume a more or less bell curve distrobution, exclusive of things like size, etc... In that, some people (now, or prior, without queues) would get them fast, and others would get them slowly. Your (pl.) arguments earlier suggest that we are "squishing" this bellcurve towards the average wait time point. This may not be as good an idea as it seems. The possibility of being on that "fast tail" of the curve is fairly appealing... -dave- -----Original Message----- From: dague12 [mailto:dague@hotmail.com] Sent: Monday, June 09, 2003 12:55 PM To: the_gdf@yahoogroups.com Subject: [the_gdf] Re: Unsolicited "QUEUE " messages --- In the_gdf@yahoogroups.com, "Dave Nicponski" wrote: Exactly my point... What, exactly, is this "fairness"? Can you give me a good mechanism for measuring/quantifying it? If not, this point isn't really valid, as it results in a "user-placebo" which, admitedly, may be better than nothing. However, be very careful when making claims like "Queues lead to fairness" and the like... Without being able to quantify this you will have a hard time demonstrating anything more than placebo effect. Queue gives fairness in the sense that everyone is going to have to wait a similar time to get the upload slot. Without queue you have an anarchy where anybody can get the slot, you might have people that get it in 1 minute, as well as people that is never able to get in. Lets examine something here... DisneyLand, say, since it was mentioned in-office on Friday as an example of "why queuing works"... Tons of (long) queues there. It is my belief that they work *only* because a ***Very High Penalty*** can be imposed for 'misbehavior' (leaving the line results in an hour or more of lost time) It is really a benefit/punishment system, right? Hmm, I wasn't pro PARQ much, but this example now convinces me that PARQ is good. Have you seen the FastPass they use, well that's a form of passive queue that you don't have to wait in line, but your line place is being kept. At the end it allows everyone to wait the same amount of time to get in. Sorry, I wrote this kind of in a hurry. Yahoo! Groups Sponsor To unsubscribe from this group, send an email to: the_gdf-unsubscribe@egroups.com Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service. ________________________________________________________________________ ________________________________________________________________________ Message: 10 Date: Mon, 9 Jun 2003 20:40:43 +0200 From: "Alejandro R. Mosteo Chagoyen" Subject: Re[2]: Re: Unsolicited "QUEUE " messages Sorry for jumping in without being a Gnutella developer, but this queuing matter interests me extraordinarily. 1) Do you want a system where the wait time for files is expected to be equally horrible and lengthy, or one where half your files finish rapidly and the other half take awhile? I would prefer the later, but my suspicion is that that's not a likely scenery in a big network with enough users and efficient sources exchange. Look at the ed2k example. I see the probable scenery more like: 1) Wait for files for lengthy times or 2) Get 99+% of the time busy responses and get frustrated and frustrated an frustrated. I think that queues simply get the chaos out of the equation. Once you have queues long enough to accommodate all (or most) requests, you can tweak them to optimize what you want: be it having queues for different file sizes, or making queues not fifo (for example prioritizing less demanded files (likely to be rare), clients who have downloaded less from you, or whatever). Without queues or with too short ones, basically you have a situation where not you nor your clients have control over the situation, and what's worst: abusers (hammering clients) do really have an advantage. This last point is enough for me to prefer queues. Kind regards. ________________________________________________________________________ Date: Mon, 09 Jun 2003 19:02:18 -0000 From: "Vinnie" Subject: Re: Unsolicited "QUEUE " messages --- In the_gdf@yahoogroups.com, "Alejandro R. Mosteo Chagoyen" wrote: Once you have queues long enough to accommodate all (or most) requests You can forget about this pipe dream right now. From our beta test network of 158 nodes, there are currently 245 active downloads (receiving data or queued) and 5,384 waiting downloads (not active transferring or queued). It is obvious that there will never be a sufficient number of queue slots. ________________________________________________________________________ ________________________________________________________________________ Message: 13 Date: Mon, 9 Jun 2003 21:18:23 +0200 From: Jann Röder Subject: AW: Re: Unsolicited "QUEUE " messages --- In the_gdf@yahoogroups.com, "Alejandro R. Mosteo Chagoyen" wrote: Once you have queues long enough to accommodate all (or most) requests You can forget about this pipe dream right now. From our beta test network of 158 nodes, there are currently 245 active downloads (receiving data or queued) and 5,384 waiting downloads (not active transferring or queued). It is obvious that there will never be a sufficient number of queue slots. That may be true, but if a client has say 5000 slots and it gives you a busy signal, you know that it is useless to retry this host in the next 24 hours or so. However I think 5000 slots will take quite some time to fill up. ________________________________________________________________________ ________________________________________________________________________ Message: 14 Date: Mon, 9 Jun 2003 21:15:16 +0200 From: "Alejandro R. Mosteo Chagoyen" Subject: Re: Re: Unsolicited "QUEUE " messages From our beta test network of 158 nodes, there are currently 245 active downloads (receiving data or queued) and 5,384 waiting downloads (not active transferring or queued). I don't understand. Is that network closed? What are the maximum queue lengths? What are the limit of occurrences of a client in the same queue? Is there a typo in one of the two "or queued"? It is obvious that there will never be a sufficient number of queue slots. However, isn't that dependent on what files are you sharing? What's the setup of your test? Everyone sharing the same, all requesting the same? Or what? In my gnutella servant I have never seen more than 70 clients queued. So in my case I've never run out of queue slots. Kind regards. ________________________________________________________________________ Date: Mon, 09 Jun 2003 21:18:26 -0000 From: "Vinnie" Subject: Re: Unsolicited "QUEUE " messages --- In the_gdf@yahoogroups.com, "Alejandro R. Mosteo Chagoyen" wrote: From our beta test network of 158 nodes ... I don't understand. Is that network closed? No the network isn't closed, but we can only count leaves/Ultrapeers, and get download statistics, from BearShare 4.3.0 servents. The users and content are typical for the Gnutella network. ________________________________________________________________________ Date: Mon, 9 Jun 2003 16:28:25 -0700 (PDT) From: Jay Heyl Subject: RE: Re: Unsolicited "QUEUE " messages --- Dave Nicponski wrote: Well, since many admittedly intellegent people see this exactly the opposite as i do, perhaps I am mistaken. Before there were any queues at all, I found it VERY difficult to actually download files. The mechanism where whoever happened to submit a download request at just the right moment was the winner just didn't work very well. You had a chance of getting your download right away, but you also had a chance of pounding that host for days and still not getting the download. With queues, if I'm willing to wait around long enough and the host is up long enough, I know I will eventually get my download. Call it the placebo effect if you want, but to me this is a much better system. While it is certainly possible to implement queues in such a way that everyone has to wait for hours and hours before they can download anything, it doesn't have to be done that way. The client I use allows the user to define as many queues as he wants and to set up rules for how transfer requests are assigned to those queues. With a single queue it's easy for small file requests to get stuck behind many large file requests and end up waiting literally days to start the download. With the multiple queue capability, I've defined one queue for very small files, one for medium size files (which I've defined to be between 256kB and 15MB), and one for large files. This has worked out very well. There is almost never anyone in line for small files. The medium size queue seldom has more than a dozen or so requests. The large queue sometimes gets a bit long, but this doesn't seem to be a huge problem as people downloading giant files are conditioned to long waits. You can certainly come up with theoretical arguments why queues might not work, but, in practice, they seem to work fairly well. Even the eDonkey queues with thousands of entries work reasonably well, at least from the perspective of actually being able to download files. (BTW, the only reason the eDonkey queues need to be that long is due to the way the clients queue up requests. Unlike the gnutella clients, the eDonkey clients queue up a download request with EVERY client they know to have the desired file. Even with this agressive queueing behavior and the alleged million eDonkey users, I've never had an eDonkey queue with more than 500 clients in line.) Given that we all know queues work quite well in the physical world and also have extensive application in the digital world, I respectfully suggest that the burden of proof that queues do NOT work should lie with those trying to argue the negative. Hand-waving arguments and simplistic real world analogies should not be taken as proof. Currently, all the major players seem to be supporting upload queues. I've even seen some Morpheus clients in my upload queue recently. With almost all of the gnutella world supporting upload queues, I haven't seen the size of my queues exploding and the file transfers are happening in an orderly manner. The real world evidence indicates that queues work. Where's the proof that they don't? As to the question of whether I'd prefer long waits or a small chance of getting some of my files right away (the 50/50 chance suggested with the question is VERY optimistic in my experience), I'll go with the long wait with a much higher assurance of actually getting something. Just one user's opinion. __________________________________ Do you Yahoo!? Yahoo! Calendar - Free online calendar with sync to Outlook(TM). http://calendar.yahoo.com ________________________________________________________________________ ________________________________________________________________________ Message: 20 Date: 10 Jun 2003 06:23:37 GMT From: Raphael_Manfredi@pobox.com Subject: Re: Unsolicited "QUEUE " messages Quoting Jay Heyl from ml.gnutella.dev-forum: :As to the question of whether I'd prefer long waits or a small :chance of getting some of my files right away (the 50/50 chance :suggested with the question is VERY optimistic in my experience), :I'll go with the long wait with a much higher assurance of :actually getting something. Just one user's opinion. Since we all seem to agree that queues are somewhat necessary, we must not forget that the vast majority of users of Gnutella use ADSL home connections, and that almost all those connections are disconnected every 24 hours, and change their IP. Therefore, Active Queueing is flawed. I've seen Shareaza queue me as slot #945/1285, with active queuing. No need to tell that there is no way I can move to slot #1 in 24 hours. Hopefully, PARQ is a viable alternative that extends Active Queueing and can cope with the interruption of the connection, as well as both a client and a server IP change (which imply a disconnection). Raphael ________________________________________________________________________ Date: Tue, 10 Jun 2003 13:50:29 -0000 From: "Vinnie" Subject: Re: Unsolicited "QUEUE " messages --- In the_gdf@yahoogroups.com, Raphael_Manfredi@p... wrote: Hopefully, PARQ is a viable alternative that extends Active Queueing and can cope with the interruption of the connection, as well as both a client and a server IP change (which imply a disconnection). I think your efforts are well-intentioned, but misplaced. The bigger problem is that files take so long to retrieve. PARQ (or remote queues) does nothing to shorten the time required to obtain a file. All it does is give the user a placebo under the guise of a "fair" upload system. What we need to do is make files easier to obtain. This can be done with a combination of the following: - Prefer uploading a complete file to one connection instead of uploading several pieces to several connections. Shareaza has a rotating slot scheme that gives each connection a subset of data before disconnecting it. This is flawed - it doesn't encourage the shortest time transfer of complete files. - Prefer uploads to faster connections over slow ones. Some servents have small,medium,and large file queues. This is an interesting idea, but it would probably be better to have queues based on connection speed. The principle is that reserving slots for very fast connections will reduce the time required to propagate a complete file (assuming the other end is sharing) - Partial file sharing, with immediate sharing of in progress downloads. Upload servers insert the IP and port of downloaders in progress into a separate PFS mesh. This is identical to the scheme used by BitTorrent - downloaders immediately share verifiable chunks as they are transferred, and the upload server propagates their information in a mesh. - Full HTTP pipelining on the download side. BearShare currently supports full pipelining on the upload side, and there remains the work of implementing it on the download side. If all servents fully pipeline requests on keepalive connections, there would be a 5% to 10% improvement in transfer times (sometimes more if the host is near its send bandwidth limit). - Forced sharing of the last N downloads. After a servent hashes a new download, it can keep the file handle open and return query hits for the file, and share the file. This prevents the user from deleting the file or moving it out of a shared directory. These files would be shared regardless of the user setting for sharing. There would be a limited number of slots, and a (small) bandwidth limit on these forced shares. This directly attacks the freeloading problem, and creates many new upload slots on the network. Forced shares would be canceled when the application exits. ________________________________________________________________________ ________________________________________________________________________ Message: 2 Date: Tue, 10 Jun 2003 10:11:08 -0400 From: "Dave Nicponski" Subject: RE: Re: Unsolicited "QUEUE " messages [quote] You can certainly come up with theoretical arguments why queues might not work, but, in practice, they seem to work fairly well. [/quote] Bah.... That is every bit as subjective as my (equally valid) comment that they do not work. [quote] Even the eDonkey queues with thousands of entries work reasonably well, at least from the perspective of actually being able to download files. (BTW, the only reason the eDonkey queues need to be that long is due to the way the clients queue up requests. Unlike the gnutella clients, the eDonkey clients queue up a download request with EVERY client they know to have the desired file. Even with this agressive queueing behavior and the alleged million eDonkey users, I've never had an eDonkey queue with more than 500 clients in line.) [/quote] Great for EDonkey! However, if we (Gnutella) cannot satisfy the rate of (content) demand now, how is indefinately queuing demand up going to help? [quote] Given that we all know queues work quite well in the physical world and also have extensive application in the digital world, I respectfully suggest that the burden of proof that queues do NOT work should lie with those trying to argue the negative. Hand-waving arguments and simplistic real world analogies should not be taken as proof. [/quote] I truly hope that you are not referring to my post. That was the result of observation and repeated hypothesis, disproval, rinse, repeat. It was also highly influenced by watching IRL people here on Lincoln Road (popular social spot) crowding in, on, and around night clubs and other social hotspots. My post was very well grounded in reality, i believe. It was not a "hand-waving argument", certainly. I have given my analysis of the situation. Accept or disprove, that is up to you. As far as I am concerned (and my vendor-body agrees with me, for the most part) is that queues are *only* a placebo. Ideologies of "fairness" aside, they do not solve any technical problems on their own merit. The most attractive part of PARQ (or any queuing system ive seen to date) is resumption of transfer after small (<5 min) downtime. [quote] Currently, all the major players seem to be supporting upload queues. [/quote] This does not imply that queues are good or not. If you took the time to read all my reasoning, it is obvious why every now implements that queuing system. To do otherwise would be foolish! (Follow the link to my posts, and look around for the terms "VIP pass" to understand why this is)... Small towns have few churches and few bars... Big cities have many churches and many bars... Does this mean that churches cause bars? Of course not! There is an independant correlation between the two, that is not expressed here (population size). Citing "All major players support queues" as evidence that "queuing is good, or even works correctly" is nonsense, as it misses the **OBVIOUS** independant correlation... (Follow my links in original post to BearShare labs if interested) [quote] I've even seen some Morpheus clients in my upload queue recently. With almost all of the gnutella world supporting upload queues, I haven't seen the size of my queues exploding and the file transfers are happening in an orderly manner. [/quote] And here you are wrong again! Except, that not only are you wrong, you are **FABRICATING EVIDENCE**! You are stating OPINION as if it were FACT!. WE have real data, hard and fast numbers that we are steadily collecting, not just "opinion" about the state of things. Vinnie gave you a teeny sample of that, with Downloads/Uplodas info. Queues aren't filling? Yeah right! Get real.... [quote] The real world evidence indicates that queues work. Where's the proof that they don't? [/quote] This statement does nothing to discount my theory as to **WHY** they (queues) *kinda* work in real life. There is a plethora of cases where queues do not really "work" as far as I am concerned. Do you consider the DMV to be "working" when it takes you 4 hours to register your car? Four hours of wasted time, where you have to sit there doing **NOTHING ELSE**?? Of course not! Its broken! Cattle like to sit in a long line forever, i don't! Anything that requires me to in general, or makes that the "natural state of things" is not helpful, anymoreso than adding a "minimum wait time: 2 hours" sign at the DMV would be... [quote] As to the question of whether I'd prefer long waits or a small chance of getting some of my files right away (the 50/50 chance suggested with the question is VERY optimistic in my experience), I'll go with the long wait with a much higher assurance of actually getting something. Just one user's opinion. [/quote] You poor poor person! You must have been "me" on that far, far other tail of the bell curve... I almost *NEVER* have these problems... Is it just me? Or does Gnutella just magically WORK for me, wherever I happen to be trying from? Must just be me! -dave- ________________________________________________________________________ ________________________________________________________________________ Message: 3 Date: Tue, 10 Jun 2003 16:10:10 +0200 From: Jann Röder Subject: AW: Re: Unsolicited "QUEUE " messages --- In the_gdf@yahoogroups.com, Raphael_Manfredi@p... wrote: Hopefully, PARQ is a viable alternative that extends Active Queueing and can cope with the interruption of the connection, as well as both a client and a server IP change (which imply a disconnection). I think your efforts are well-intentioned, but misplaced. The bigger problem is that files take so long to retrieve. PARQ (or remote queues) does nothing to shorten the time required to obtain a file. All it does is give the user a placebo under the guise of a "fair" upload system. I don't think it is a placebo. It reduces file requests and it makes sure that you can downlaod after you wait for some time, which is not garuanteed without queues. Without queues you have to be agressive to get what you want, and we don't want to be agressive on the Gnutella network, do we ? - Prefer uploading a complete file to one connection instead of uploading several pieces to several connections. Shareaza has a rotating slot scheme that gives each connection a subset of data before disconnecting it. This is flawed - it doesn't encourage the shortest time transfer of complete files. Of course this system only works if the client also offers Partial File Sharing. The rotating slot system makes sure that more people get parts of the file and by doing this many upload slots are created. I think this does much to help the distribution of large files. - Prefer uploads to faster connections over slow ones. Some servents have small,medium,and large file queues. This is an interesting idea, but it would probably be better to have queues based on connection speed. The principle is that reserving slots for very fast connections will reduce the time required to propagate a complete file (assuming the other end is sharing) How would you determine the connection speed of the other end ? I'd rather prefer uplaoding to clients that support PFS. And it is a good idea to prefer uplaoding files that you are currently downloading. eMule has put this idea a bit further by giving priorities to your files depending on how wide spread they are. And it seems to work (at least for me). - Partial file sharing, with immediate sharing of in progress downloads. Upload servers insert the IP and port of downloaders in progress into a separate PFS mesh. This is identical to the scheme used by BitTorrent - downloaders immediately share verifiable chunks as they are transferred, and the upload server propagates their information in a mesh. True... very impoartant - Forced sharing of the last N downloads. After a servent hashes a new download, it can keep the file handle open and return query hits for the file, and share the file. This prevents the user from deleting the file or moving it out of a shared directory. These files would be shared regardless of the user setting for sharing. There would be a limited number of slots, and a (small) bandwidth limit on these forced shares. This directly attacks the freeloading problem, and creates many new upload slots on the network. Forced shares would be canceled when the application exits. Well this would be even stronger than forced PFS, but I like the idea, but I'm sure others don't. Jann ________________________________________________________________________ ________________________________________________________________________ Message: 4 Date: Tue, 10 Jun 2003 16:27:18 +0200 From: "Mathias Bollaert" Subject: Re: Re: Unsolicited "QUEUE " messages ----- Original Message ----- From: "Vinnie" . - Forced sharing of the last N downloads. After a servent hashes a new download, it can keep the file handle open and return query hits for the file, and share the file. This prevents the user from deleting the file or moving it out of a shared directory. These files would be shared regardless of the user setting for sharing. There would be a limited number of slots, and a (small) bandwidth limit on these forced shares. This directly attacks the freeloading problem, and creates many new upload slots on the network. Forced shares would be canceled when the application exits. I'm not absolutely sure about this, but I think this will only work under MS OS (at least in Java). But I like the idea. M. ________________________________________________________________________ Date: Tue, 10 Jun 2003 14:48:31 -0000 From: "Vinnie" Subject: Re: Unsolicited "QUEUE " messages --- In the_gdf@yahoogroups.com, Jann Röder wrote: I don't think it is a placebo. It reduces file requests and it makes sure that you can downlaod after you wait for some time, which is not garuanteed without queues. Untrue. If the average queue wait time is longer than the average uptime, you will lose the queue position when the servent goes offline (yes, this happens). When you use words like "guarantee", what I am hearing is that you are trying to fulfill a psychological need (i.e. you want more certainty that you will get the file, even if you have to wait a long time). Your claim that queueing reduces file requests is completely false. You are a victim of selective observation - you are ignoring the download requests that receive a Busy result because the queue on the other end is full. You are only paying attention on the sources which go into a queued state. This is human nature - you WANT to think queues help, so you only look at the cases where you feel they are working. Without queues you have to be agressive to get what you want, and we don't want to be agressive on the Gnutella network, do we ? Why do you have to be aggressive? It is easy to return Busy to IP addresses which re-request too frequently. Also note, that the Vestibule Problem STILL EXISTS! Queuing doesn't remove incentive for aggression, it just moves it from the end of the upload slots to the end of the queue (i.e. servents will hammer a host whose queue is full so they can squeak to the end of the line before someone else). - Prefer uploads to faster connections over slow ones. How would you determine the connection speed of the other end ? There are many ways, here is one: queue a few connections, and give each of them a couple of minutes of transfer before queueing them again. After several connections have received transfer, favor the faster one, and put the other connections into a medium or slow queue. - Forced sharing of the last N downloads. Well this would be even stronger than forced PFS, but I like the idea, but I'm sure others don't. It would be stronger in some ways, yes, but PFS and forced sharing of the last N downloads are complementary. I agree, it is a sensitive subject. On the other hand, if it was OK for a user to download the file, I think it is morally acceptible to force them to share it, for at least a little while, and with an upper limit on resource usage. ________________________________________________________________________ Date: Tue, 10 Jun 2003 14:53:40 -0000 From: "smike82j" Subject: Re: Unsolicited "QUEUE " messages --- In the_gdf@yahoogroups.com, "Vinnie" wrote: - Prefer uploading a complete file to one connection instead of uploading several pieces to several connections. Shareaza has a rotating slot scheme that gives each connection a subset of data before disconnecting it. This is flawed - it doesn't encourage the shortest time transfer of complete files. I am convinced there is a place for this approach. It should not be applied to everything of course (and Shareaza doesn't), but there are some situations where it can be very beneficial -- specifically when uploading partially downloaded files. Here the objective is not to get complete files out there (which would not be possible anyway -- you don't have the complete file locally), but to maximise the efficient spread of the file data. I think BitTorrent does pretty well in this respect, and it does it by stopping and starting a bunch of active upload connections based on certain criteria. A linear queue is a simpler case of that, but the concept of giving each host a high-speed turn to grab a verifyable chunk they can reshare then moving on to the next host is the same. Letting hosts leech away at a file for as long as they like is not efficient when content is dissipating quickly from a small number of complete sources to a large number of incomplete sources. - Prefer uploads to faster connections over slow ones. Some servents have small,medium,and large file queues. This is an interesting idea, but it would probably be better to have queues based on connection speed. The principle is that reserving slots for very fast connections will reduce the time required to propagate a complete file (assuming the other end is sharing) I agree, although the metric is similar. What we're really trying to do there is categorise based on the expected time to complete the file. We don't want transfers that could complete very quickly having to wait behind transfers that will take hours or days -- at least in the case where you get unrestricted access at the head of the queue. Ignoring all other factors, categorising based on file size is a reasonable start, and seems to work pretty effectively in Shareaza. Taking into account connection speed as well would improve it. The concept of files can be disregarded entirely and behaviour determined purely on transfer speed, but this does present some challenges in an environment where many files are being offered. Shareaza is a bit queue-happy at the moment, and if anything may be over-categorising things, but I think it's moving in the right direction. - Partial file sharing, with immediate sharing of in progress downloads. Upload servers insert the IP and port of downloaders in progress into a separate PFS mesh. This is identical to the scheme used by BitTorrent - downloaders immediately share verifiable chunks as they are transferred, and the upload server propagates their information in a mesh. In the system used by Shareaza it is the responsibility of the downloader to insert itself into the source list, which it does as soon as it has received enough file data. This gives a bit more control to make sure the downloader is only listed once it has enough of the file to reliably share, and if it knows it is contactable. I also use a single source mesh rather than a dual system.. we had a debate about that before that should be easy enough to dig up. In summary I felt that is the way to go, others disagreed. - Full HTTP pipelining on the download side. BearShare currently supports full pipelining on the upload side, and there remains the work of implementing it on the download side. If all servents fully pipeline requests on keepalive connections, there would be a 5% to 10% improvement in transfer times (sometimes more if the host is near its send bandwidth limit). That's pretty much the story in Shareaza's HTTP implementation as well, and I agree that pipelining requests is a good move. Shareaza to Shareaza transfers in the other two transfer protocols it supports at the moment (both of which use pipelining) are noticably faster than those which use HTTP as a result of this. HTTP can benefit similarly, although its overhead is still going to be higher thanks to the overhead of the requests and responses. I've been giving some thought to abbreviated requests and responses that omit all but the most critical of headers -- Shareaza already omits several headers on header blocks after the first, however even more can be ommitted when the same file is being requested (perhaps even the URN, although that's starting to get very messy). ________________________________________________________________________ ________________________________________________________________________ Message: 9 Date: Tue, 10 Jun 2003 15:07:13 -0000 From: "Raphael Manfredi" Subject: Re: Unsolicited "QUEUE " messages --- In the_gdf@yahoogroups.com, "Vinnie" wrote: --- In the_gdf@yahoogroups.com, Jann Röder wrote: I don't think it is a placebo. It reduces file requests and it makes sure that you can downlaod after you wait for some time, which is not garuanteed without queues. Untrue. If the average queue wait time is longer than the average uptime, you will lose the queue position when the servent goes offline (yes, this happens). It depends on the queue. PARQ does not. Your claim that queueing reduces file requests is completely false. Vinnie, it is completely true with PARQ. With a large queue, there is no busy result in practice. And if 4000 entries per queue is not enough, let's grow the limit. Raphael ________________________________________________________________________ Date: Tue, 10 Jun 2003 17:20:59 +0200 From: "Alejandro. R. Mosteo Chagoyen" Subject: Re[2]: Re: Unsolicited "QUEUE " messages However, if we (Gnutella) cannot satisfy the rate of (content) demand now, how is indefinately queuing demand up going to help? What's so great about not queuing? If you queue, you stabilize the situation. You are establishing an order. If you don't queue, you are allowing randomness to enter the game. I have given my analysis of the situation. Accept or disprove, that is up to you. As far as I am concerned (and my vendor-body agrees with me, for the most part) is that queues are *only* a placebo. So, to be clear, you just say that if nobody were implementing queues, we would be *exactly* equal than with queues? Please confirm that. That's what I understand from your phrase. Ideologies of "fairness" aside, they do not solve any technical problems on their own merit. They solve the problem of uncertainty. That's not a problem? They completely remove the problem of *not knowing at all* when you are going to start a download. See below for more "technical" aspects which queues resolve. The most attractive part of PARQ (or any queuing system ive seen to date) is resumption of transfer after small (<5 min) downtime. I agree here, that's a need for current queuing systems. Note that ed2k has partly advanced in this aspect. I'm not sure if its queues can survive to a IP change, but being UDP based they certainly resist to connection drops. This does not imply that queues are good or not. If you took the time to read all my reasoning, it is obvious why every now implements that queuing system. To do otherwise would be foolish! Yes, once queues are in place, not supporting them is your lose. But, again, I need to know if you absolutely believe that no queues at all is equally efficient to queues for everybody. Citing "All major players support queues" as evidence that "queuing is good, or even works correctly" is nonsense, as it misses the **OBVIOUS** independant correlation... (Follow my links in original post to BearShare labs if interested) For me, is self-evident and intuitive that when demand is high, queues are an improvement over no queues. For you, it seems not to be the case, if I understand correctly. I've read the thread mentioned at bearshare and I don't remember any hard proof there too, just the same believing that large queues are a hassle. How is that queues are great (read: necessary) in many domains (CPU task scheduling, real life) to prevent undesired behavior (starvation, indefinite preemption), and not for Gnutella? Do you think that these misbehaviors are not undesired in a p2p network? It's a placebo to prevent them? There *is* a difference between queues and no queues. And that difference is certainly for me no worst than no queues. I have not seen exposed any advantage on not having queues, except that "waiting is bad, I prefer no wait", like removing queues would remove somewhat the wait. You want Gnutella to be the best p2p network and are saying that its users are better *not knowing at all* if its uptime is going to help them? That they must try indefinitely requesting to a client instead of knowing that they may be near to start or far away from start? I can't believe you consider that placebo. That's a real advantage. For me, eliminating indeterminate order of upload is far from being a placebo. (...) Vinnie gave you a teeny sample of that, with Downloads/Uplodas info. Queues aren't filling? Yeah right! Get real.... If you refer to the 15x network that Vinnie mentioned yesterday, I questioned some things to really understand how queues were filling, and that was not answered. I have not seen my queues filled, and that's also fact and not fabrication. This statement does nothing to discount my theory as to **WHY** they (queues) *kinda* work in real life. *kinda*? How can one go to buy at the market without queues? With an axe? Is there a better solution not being implemented only by pure malice on the sellers? They amuse our waits? (Note I'm enjoying this conversation, not saying you're a fool or something. I feel a real attraction to someday understand why queue detractors still exist ;-) I need to understand what you understand for real life queues not working. I think they work. I don't like the wait, but I don't see a better solution. There is a plethora of cases where queues do not really "work" as far as I am concerned. Do you consider the DMV to be "working" when it takes you 4 hours to register your car? Four hours of wasted time, where you have to sit there doing **NOTHING ELSE**?? Well, for me a date given by the doctor is in essence a queue in what you don't need to be present, so you can do other things until time arrive. Better enough if it's my computer who does the wait. I see that as a strong similarity with p2p queues, where you simply note from time to time that you're still alive. I don't keep looking at my screen to see how I advance in queues. The main change in the POV is that these four hours of wait are no waste, as you say. In fact, these are what buy you the download, contrarily to *not download, maybe, never*. I almost *NEVER* have these problems... Is it just me? Or does Gnutella just magically WORK for me, wherever I happen to be trying from? Certainly your experience differs from mine. Pre-queue times... uh. My base point is that between chaos and no chaos, I prefer no chaos. Please convince me that queues in reality don't remove disorder. You can say: servers go offline, the mean uptime is bla; the queues will be never long enough... but that's only the *worst* case. What if people get used to long uptimes or technology allows it? What if you are sharing a rare file and can guarantee a client their order of upload? You still maintain that's no real advantage? Kind regards. ________________________________________________________________________ ________________________________________________________________________ Message: 12 Date: Tue, 10 Jun 2003 17:20:38 +0200 From: Jann Röder Subject: AW: Re: Unsolicited "QUEUE " messages Your claim that queueing reduces file requests is completely false. Vinnie, it is completely true with PARQ. With a large queue, there is no busy result in practice. And if 4000 entries per queue is not enough, let's grow the limit. I was just about to say that. Jann ________________________________________________________________________ ________________________________________________________________________ Message: 13 Date: Tue, 10 Jun 2003 11:23:42 -0400 From: "Dave Nicponski" Subject: RE: Re: Unsolicited "QUEUE " messages [QUOTE] I don't think it is a placebo. It reduces file requests *********> and it makes sure that you can downlaod *********> after you wait for some time, which *********> is not garuanteed without queues. [/QUOTE] I does that, really? OK lets analyze.... PREMISE 1: Queue slot give is intended as a low bandwidth, low resource-consuming route which leads monotonically towards an active transfer slot. NOTES: 1) A queued client which finishes the queued file via other means will remove themselves from a queue. 2) Even if the majority of the time, a queued downloaded sits idle, and periodically creates little bandwidth "spikes" as he(or we) check back in, this can be represented by an even smaller average bandwidth... 2a) Example: 10 queued downloaders each sit idle for 9 seconds, and each transmit 1000 bytes in the 10th. This is (for this argument) equivelent to each of those 10 downloaders using 100 Bytes/second each, or a really slow download speed. 3) Bandwidth devoted to queue "re-requests" do not contribute towards file download directly. Instead, it is used for AltLocs, headers, queue status update, etc. 4) A QUEUE slot is **NOTHING MORE** than a glorified, slow, upload slot, because: 4a) In both QUEUESLOTS and FILESLOT cases, a downloader may stop downloading early if the file is completed elsewhere 4b) The desired intention in each case is to transfer file byets 4c) Blocking points: (Queue Retry time == Download RetryAfter time) 4d) In a fully working case, after discrete time N, an queue slot will "magically become" an upload slot, causing file to begin to transfer. 4e) Ideal queue case from (4d) is N=0, or no wait time. PREMISE 2: On GNUTELLA, as a network, there is a severe discrepancy between bandwidth supply and bandwidth demand. Demand must be much higher than supply, or we wouldn't be having this discussion... NOTES: There are several reasons for this: 5) Human Nature: As long as some people want to CONSUME but not CONTRIBUTE this will occur 6) ISP technology: ADSL has downloads CONSUMPTION potential 3x-5x greater than the uploads CONTRIBUTION potential 7) Program Uptime Charecteristics: People tend to close the Gnutella program when the DOWNLOADS complete, not the UPLOADS PREMISE 3: Adding QUEUE slots to the network is ****STRICTLY EQUIVELENT**** to adding upload slots, in the general case. Any distinction between the two is artificial/semantical in nature. They both accomplish the same thing (and, for instance, in BearShare code, they are actually the same implementation!) See NOTES 5-7 for why ****************** Now, the important part: REASONING, FROM A TO B: 1) Inherantly in todays GNUTELLA, content and resource DEMAND exceeds content and resource SUPPLY. 2) This inherant problem DOES NOT EXIST SOLELY as a "software" problem; there are real world, physical reasons for this to be the case. 3) Adding an upload slot (SLOW QUEUE slot or FAST UPLOAD slot) to a person who is **ALREADY UPLOADING** does NOT add content/resources to the network. 4) MASSIVELY adding queue/upload slots to the network has this as the ONLY MAJOR, PROVABLE effect: Average Resource consumed/available (PER SLOT) is going to go DOWN!!! Average transfer time per UPLOAD slot is going to go UP. CONCLUSION: The underlying problem which is CAUSING busies, slow/failed downloads, etc, is NOT ADDRESSED AT ALL by queuing system. Therefore, queuing system (even PARQ) is at mest nominal in any *improvements* to the network. More likely, they are **COMPLETELY** placebo in nature. Let the flames begin... -dave- ________________________________________________________________________ ________________________________________________________________________ Message: 14 Date: Tue, 10 Jun 2003 11:27:36 -0400 From: "Dave Nicponski" Subject: RE: Re[2]: Re: Unsolicited "QUEUE " messages [QUOTE] I've read the thread mentioned at bearshare and I don't remember any hard proof there too, just the same believing that large queues are a hassle. [/QUOTE] Not well enough, obviously.. More than just that thread will be necessary to read if you want the full, complete, painstaking analysis that we and beta testers went through. I repeated many of them in my most recent (other) post here. -dave- ________________________________________________________________________ ________________________________________________________________________ Message: 15 Date: Tue, 10 Jun 2003 17:44:03 +0200 From: Jann Röder Subject: AW: Re: Unsolicited "QUEUE " messages @ dave: You are right if there where only active queues. But PARQ also has passive queues which do not require an active connection and are therefore not to be considered as a slow uplaod slot. Imagine this: A passive queue slot is like having an appointment with a doctor. An active queue slot is like sitting in the waiting room. Of course it is useless to have the waiting room full with people. And I think we shouldn't discuss here whether queues are good or bad because we can't remove them anyway. How could we force all vendors to remove their queue support ? I think we should discuss whether PARQ is better than the current system. Together with Vinnie's suggestions to improve the upload situation we can make Gnutella better. @ Vinnie: - Prefer uploads to faster connections over slow ones. How would you determine the connection speed of the other end ? There are many ways, here is one: queue a few connections, and give each of them a couple of minutes of transfer before queueing them again. After several connections have received transfer, favor the faster one, and put the other connections into a medium or slow queue. I doubt that this will work in the real Gnutella world. There are too many factors that have an impact on transfer speed. What if the user starts uploading to his FTP server ? Or if he has a fast download going. Both will have an impact on his upload speed and therefor any measure of the upload speed will be inaccurate. Without queues you have to be agressive to get what you want, and we don't want to be agressive on the Gnutella network, do we ? Why do you have to be aggressive? Because then you'll have a higher chance to get an uplaod / queue slot. You're right with the current active queue system the problem is just moved to the end of the queue, that's why I think PARQ is a good idea. Jann ________________________________________________________________________ ________________________________________________________________________ Message: 16 Date: Tue, 10 Jun 2003 17:51:11 +0200 From: "Alejandro. R. Mosteo Chagoyen" Subject: Re[2]: Re: Unsolicited "QUEUE " messages CONCLUSION: The underlying problem which is CAUSING busies, slow/failed downloads, etc, is NOT ADDRESSED AT ALL by queuing system. Therefore, queuing system (even PARQ) is at best nominal in any *improvements* to the network. More likely, they are **COMPLETELY** placebo in nature. And again I must say: *) Removing the possibility of infinite starvation for a client, caused by other, allied or not, clients, is a gain that justifies by far the incurred penalty of maintaining queues. That's a *real* and not *nominal* improvement for the network *users*. So work addressed to improve queues "wasted" resources (like PARQ) are a real technical improvement, and since I don't foresee a near future where everyone has unlimited upload capacity, some solution must be provided, and for now no other than queues is in use (that I know). I must admit: when I talk about large queues, I'm thinking about the optimal, ideal, not resource-costly queues, because I see that as a goal. Your post addresses these real-implementation concerns. You don't mention, however, my concerns about starvation. I understand you dismiss them as placebo, or "fairness" non-technological problem? I don't think a p2p system should forget about that. The ultimate purpose of a p2p network is to provide its clients their requests, and you're saying that giving not any theoretical guarantee, even if it sometimes can fail, is OK? I must disagree. I'm equally interested in the real costs of queues, however, because I think they must be addressed as an obligatory step to better p2p experience. I would better understand that you complaint about making queues larger but not more efficient, that's certainly a bad recipe, but that's precisely what PARQ addresses. ________________________________________________________________________ ________________________________________________________________________ Message: 17 Date: Tue, 10 Jun 2003 15:54:55 -0000 From: "Raphael Manfredi" Subject: Re: Unsolicited "QUEUE " messages --- In the_gdf@yahoogroups.com, "smike82j" wrote: HTTP can benefit similarly, although its overhead is still going to be higher thanks to the overhead of the requests and responses. I've been giving some thought to abbreviated requests and responses that omit all but the most critical of headers -- Shareaza already omits several headers on header blocks after the first, however even more can be ommitted when the same file is being requested (perhaps even the URN, although that's starting to get very messy). Are you sure optimizing HTTP requests / responses is a good idea? If you start requesting 16 KB chunks, yes, it my prove to be a problem. At most, the HTTP request / reply should use 3K total. With 512 KB chunks requested (a very small request by my book), that's less than 0.6% overhead. Come on! If this is becoming the overhead for you, you're requesting too small chunks of data. Servents should at least request 512 KB. I've configured my servent to request 25 MB at minimum. Yes, that means the whole file if the file I want is less than 25 MB and there is only one source. Raphael ________________________________________________________________________ ________________________________________________________________________ Message: 18 Date: Tue, 10 Jun 2003 12:05:18 -0400 From: "Dave Nicponski" Subject: RE: Re: Unsolicited "QUEUE " messages NOTHING that i said is differant with PARQ: 1) It does NOT add resources 2) It IS an upload slot, whether a connection is maintained or not. In fact, it is EXACTLY like a pre-KeepAlive upload slot. Being "passive" doesn't make it differant. 3) Your comparison with the doctor analogy is a good starting point... If we assume that the **RATE OF DEMAND** for the doctor *CAN* be satisfied by said doctor by making appointments, without external supply being added (more doctors), then his *****RATE OF SUPPLY***** exceeds his *****RATE OF DEMAND***** THIS IS THE KEY POINT! It has NOTHING to do with active/passive/whatever crap. It is precisely BECAUSE the doctor's RATE OF SUPPLY exceeds or meets the RATE OF DEMAND that the queuing system (appointments) works! This EXCEED RATE OF DEMAND property requires that he KEEPS THE DOCTORS OFFICE OPEN until all patients are satisified, as well. If your doctor (or bank) made you leave at 5pm because you were still IN LINE, WAITING then you could NOT make the claim that the queuing system works. Even more in the Doctor's favor, while you are waiting in the waiting room of Doctor XYZ, you CANNOT also be in the waiting room of Doctor ABC. This is yet another example in the *real world cases* why queue may be appropriate: The entire system is DESIGNED to cause DEMAND to be limited to the available SUPPLY, and then enforcing SUPPLY to last until all of a given DEMAND is met. This CANNOT BE ENFORCED in gnutella! As long as I can sit in Raphiel's queue AND Vinnie's queue AND Mario's queue AND Philippes queue, etc, this WILL NOT work because RATE OF DEMAND has not been in any way curbed, or even placated! This is DrOffice (real world) case is NOT THE CASE in Gnutella. RATE OF DEMAND is whole magnitutdes larger than RATE OF SUPPLY, and queuing (yes, even PASSIVE queuing) does NOT change this! Passive != NonUpload... Passive MAYBE == less resource intensive, but it is still an upload slot, plain and simple. If it ISNT one, because it is passive, as you claim, what is the FUNDAMENTAL difference? So far, only arguments have been "Ahh but this is passive, so it isn't the same" without detailing WHY it isn't... 1 more unread GDFs have appeared in my inbox though, so who knows... =) -dave- @ dave: You are right if there where only active queues. But PARQ also has passive queues which do not require an active connection and are therefore not to be considered as a slow uplaod slot. Imagine this: A passive queue slot is like having an appointment with a doctor. An active queue slot is like sitting in the waiting room. Of course it is useless to have the waiting room full with people. ________________________________________________________________________ ________________________________________________________________________ Message: 19 Date: Tue, 10 Jun 2003 16:12:13 -0000 From: "Raphael Manfredi" Subject: Re: Unsolicited "QUEUE " messages --- In the_gdf@yahoogroups.com, "Dave Nicponski" wrote: NOTHING that i said is differant with PARQ: 1) It does NOT add resources 2) It IS an upload slot, whether a connection is maintained or not. In fact, it is EXACTLY like a pre-KeepAlive upload slot. Being "passive" doesn't make it differant. 3) Your comparison with the doctor analogy is a good starting point... If we assume that the **RATE OF DEMAND** for the doctor *CAN* be satisfied by said doctor by making appointments, without external supply being added (more doctors), then his *****RATE OF SUPPLY***** exceeds his *****RATE OF DEMAND***** THIS IS THE KEY POINT! It has NOTHING to do with active/passive/whatever crap. From the above, I gather that your problem is not with queueing, but with the rate of supply on Gnutella being less than the rate of demand. I could not agree more. We need more people that share than we need leechers. We need to increase the supply. But stop shooting at queueing systems, and to PARQ in particular. I know PARQ is not going to solve the supply shortage, but it solves many problems: fairness, hammering, IP changes and other brutal disconnects. Raphael ________________________________________________________________________ ________________________________________________________________________ Message: 20 Date: Tue, 10 Jun 2003 18:15:06 +0200 From: "Philippe Verdy" Subject: Re: Re: Unsolicited "QUEUE " messages From: "Dave Nicponski" NOTHING that i said is differant with PARQ: 1) It does NOT add resources 2) It IS an upload slot, whether a connection is maintained or not. In fact, it is EXACTLY like a pre-KeepAlive upload slot. Being "passive" doesn't make it differant. 3) Your comparison with the doctor analogy is a good starting point... If we assume that the **RATE OF DEMAND** for the doctor *CAN* be satisfied by said doctor by making appointments, without external supply being added (more doctors), then his *****RATE OF SUPPLY***** exceeds his *****RATE OF DEMAND***** THIS IS THE KEY POINT! It has NOTHING to do with active/passive/whatever crap. That's a key argument. Adding an additional queue system will effectively not solve the problem. It seems more urgent to use other systems to meet the demand by increased supplies: - Push proxies: more hosts to download from, with a better distribution of the pushed content. - Passive content caches in proxies: less drain on pushing servents that can upload their content to more locations - Fragmented contents: a better and faster distribution to more hosts, in order to free upload slots faster The PARQ proposal is still valuable to let the new system work more smoothly, and limiting the congestion of only a few supplies. ________________________________________________________________________ ________________________________________________________________________ Message: 21 Date: Tue, 10 Jun 2003 16:21:51 -0000 From: "Vinnie" Subject: Re: Unsolicited "QUEUE " messages --- In the_gdf@yahoogroups.com, "Raphael Manfredi" wrote: But stop shooting at...PARQ... it solves many problems: fairness, hammering, IP changes and other brutal disconnects. There is always the danger of "solving" problems that are irrelevant, and burdening ourselves with overengineered solutions. Note that we've already solved these problems using different, simpler techniques that don't require collaboration between vendors: 1) Fairness, hammering Easily solved by keeping an IP address history, and returning Busy to nodes which request too often. No changes required in other vendor's code, and no protocol documentation needed. 2) IP Changes Is this really a problem Raphael? I wonder how FastTrack deals with it (hint: it doesn't). 3) Other "brutal disconnects" Another marginal problem. But BearShare solves this by keeping the slot reserved for 15 seconds after the host disconnects abnormally (in BearShare, these uploads turn red and show "Reserved" for the status). Again, no changes required in other vendor's code, and no protocol documentation needed. As long as servents immediately re- connect after losing a download source, this change is backward compatible. ________________________________________________________________________ ________________________________________________________________________ Message: 22 Date: Tue, 10 Jun 2003 12:30:31 -0400 From: "Dave Nicponski" Subject: RE: Re: Unsolicited "QUEUE " messages [QUOTE] From the above, I gather that your problem is not with queueing, but with the rate of supply on Gnutella being less than the rate of demand. I could not agree more. We need more people that share than we need leechers. We need to increase the supply. But stop shooting at queueing systems, and to PARQ in particular. I know PARQ is not going to solve the supply shortage, but it solves many problems: fairness, hammering, IP changes and other brutal disconnects. Raphael [/QUOTE] I believe that to be the fundamental problem here; one which (obviously) people think queuing is intended to solve, which it isn't and won't. Simple as that. I *DO* believe that queuing is useful because: 1) It provides a nice placebo effect to user ( Queued 118/220 looks nicer than "Busy" ) 2) has the aforementioned short-outage recovery 3) For legitimate clients, certain types of behaviors can be enforced for this specific (queued) conenction. I *DO NOT* believe that queuing is useful because: 1) Making files more reliable. This is closely tied to the fundamental problem above, which is the root CAUSE of files being hard to find. Since queues do not address this, they cannot hope to solve that problem. 2) Average wait time for a given transfer slot goes up. 3) It provides an entry barrier into the Gnutella Developer game... AKA in order to effectively compete with established vendors, a new player must now code an entire Gnutella client **AND a download queuing system**. Without this additional step, now, his client is useless, as it will ALWAYS do worse than the QUEUE enabled systems. 4) The "FAIRNESS" of file transfers: This whine is brought up here REPEATEDLY in reference to queues. ITS NOT FAIR! Why should person A get a file before me when I asked an hour ago? ITS NOT FAIR!!!! **BOO HOO HOO** My 8 year old brother whines and complains about this "Its Not Fair" junk... My 18 year old brother realizes this is TheWayThingsWork(tm) and tries to make the most of it, using the "Its Not Fair" principle to his advantage, when he can. I got news for ya: LIFE ISNT FAIR! NOR SHOULD IT BE! If it should be, evolution would not require population turnover, and everyone would get to procreate equally. Yet, I don't see you holding up a picket sign saying "Sex rates are unfair, it should be first come first serve. If I wait an hour for sex, why should JoeShmoe and his girl get to do it right now?"! heh, maybe it should work that way... To LUNCH with me, I say... -dave- ________________________________________________________________________ ________________________________________________________________________ Message: 23 Date: Tue, 10 Jun 2003 18:44:38 +0200 From: "Alejandro. R. Mosteo Chagoyen" Subject: Re: Re: Unsolicited "QUEUE " messages There is always the danger of "solving" problems that are irrelevant, and burdening ourselves with overengineered solutions. I must agree with Vinnie about this comments. I've mentioned PARQ in my posts because it is in the domain of improving queues, not as the holy grail. However, things that can be solved locally (like slot resistance to drops) don't need a new specification, and I don't like the QUEUE callback. These features, however, should have a place in the "work-route" for new servants that somebody was designing some time ago. As a side note, I have a Gnutella servant in good stages development that I expect to make available soon, so you can consider now my posts on-topic. My servant also transparently implements persistent slots like Bearshare. ________________________________________________________________________ ________________________________________________________________________ Message: 24 Date: Tue, 10 Jun 2003 18:51:01 +0200 From: Jann Röder Subject: AW: Re: Unsolicited "QUEUE " messages 3) It provides an entry barrier into the Gnutella Developer game... AKA in order to effectively compete with established vendors, a new player must now code an entire Gnutella client **AND a download queuing system**. Without this additional step, now, his client is useless, as it will ALWAYS do worse than the QUEUE enabled systems. This is solved by PARQ, you only have to obey the retry-after header. 4) The "FAIRNESS" of file transfers: This whine is brought up here REPEATEDLY in reference to queues. ITS NOT FAIR! Why should person A get a file before me when I asked an hour ago? ITS NOT FAIR!!!! **BOO HOO HOO** I don't get your point here. A person A should get the file before you only if he asked more than an hour ago. This is possible with PARQ. Of course PARQ doesn't solve the problem that there are too few resources on Gnutella, but there is not that much we can do about it, and I agree queues don't help (much) to solve this problem. Jann ________________________________________________________________________ ________________________________________________________________________ Message: 25 Date: Tue, 10 Jun 2003 18:56:04 +0200 From: "Alejandro. R. Mosteo Chagoyen" Subject: Re[2]: Re: Unsolicited "QUEUE " messages 4) The "FAIRNESS" of file transfers: This whine is brought up here REPEATEDLY in reference to queues. ITS NOT FAIR! Why should person A get a file before me when I asked an hour ago? ITS NOT FAIR!!!! **BOO HOO HOO** Why not have fairness as an objective? I would not want to use an unfair p2p system. Why you don't remove the upload queue in Bearshare? You are forced to maintain it for downloading, but nobody (you say) has the right to be queued in your servant. Do the default Bearshare queue of 0 length. Maybe others will follow your example when they see the advantages. My 18 year old brother realizes this is TheWayThingsWork(tm) and tries to make the most of it, using the "Its Not Fair" principle to his advantage, when he can. Okay, you recommend I try to abuse Gnutella as long as I can hide it from you? Are you simply making a "golpe de efecto" or you really believe I should abuse everything I can? Because I see many unfairness daily, but also don't try to promote it. Quite the contrary. I got news for ya: LIFE ISNT FAIR! NOR SHOULD IT BE! I'm glad to be in another neighborhood ;-) ________________________________________________________________________ Date: Tue, 10 Jun 2003 16:54:51 -0000 From: "Raphael Manfredi" Subject: Re: Unsolicited "QUEUE " messages --- In the_gdf@yahoogroups.com, "Vinnie" wrote: Note that we've already solved these problems using different, simpler techniques that don't require collaboration between vendors: Note that PARQ does not require any cooperation either, as long as you comply with HTTP. You'll just be passively queued, that's all. Now to the points you exerpted from my earlier message: 1) Fairness, hammering Easily solved by keeping an IP address history, and returning Busy to nodes which request too often. No changes required in other vendor's code, and no protocol documentation needed. Right for excessive hammering. But that does not handle "fairness". Although life is not necessarily fair, where is it written that the computer world has to mimic every aspect of real life? I don't care whether real life is fair or not, this is not the debate. I'm maybe an idealist (well, I write open-source software after all), but why can't we strive to add fairness in the computer world, if we can? 2) IP Changes Is this really a problem Raphael? I wonder how FastTrack deals with it (hint: it doesn't). Well, it is for me you see, when my ISP disconnects me every 24 hours, and my IP changes. There are times where I cannot move to slot #1 during the time I'm actively queued. And even when I can, maybe I'll have only 2 hours before the forced disconnection. So for ME it is important. What FastTrack does is irrelevant. 3) Other "brutal disconnects" Another marginal problem. But BearShare solves this by keeping the slot reserved for 15 seconds after the host disconnects abnormally (in BearShare, these uploads turn red and show "Reserved" for the status). Again, no changes required in other vendor's code, and no protocol documentation needed. As long as servents immediately re- connect after losing a download source, this change is backward compatible. Hmm... 15 seconds is way too short. GTKG will wait ~60 seconds in case the connection crashes, to let the other end restart the servent, in case it is the one who crashed. And to avoid hammering if the remote servent explicitly killed the upload. Raphael ________________________________________________________________________ ________________________________________________________________________ Message: 2 Date: Tue, 10 Jun 2003 16:55:52 -0000 From: "Vinnie" Subject: Re: Unsolicited "QUEUE " messages --- In the_gdf@yahoogroups.com, Jann Röder wrote: 3) It provides an entry barrier into the Gnutella Developer game... ... This is solved by PARQ, you only have to obey the retry-after header. What about the upload side? What about accepting QUEUE connect-backs? ________________________________________________________________________ ________________________________________________________________________ Message: 3 Date: Tue, 10 Jun 2003 16:58:26 -0000 From: "Raphael Manfredi" Subject: Re: Unsolicited "QUEUE " messages --- In the_gdf@yahoogroups.com, "Vinnie" wrote: --- In the_gdf@yahoogroups.com, Jann Röder wrote: 3) It provides an entry barrier into the Gnutella Developer game... ... This is solved by PARQ, you only have to obey the retry-after header. What about the upload side? What about accepting QUEUE connect-backs? You should not get QUEUE callbacks if you did not advertise PARQ. It was a bug in the early GTKG implementation that it happened. The only downside to that is that you might not be able to contact the server if you don't handle QUEUE, either because its IP has changed or because it is firewalled, and the push route was long lost. Raphael ________________________________________________________________________ ________________________________________________________________________ Message: 4 Date: Tue, 10 Jun 2003 17:08:14 -0000 From: "Vinnie" Subject: Re: Unsolicited "QUEUE " messages --- In the_gdf@yahoogroups.com, "Raphael Manfredi" wrote: --- In the_gdf@yahoogroups.com, "Vinnie" wrote: --- In the_gdf@yahoogroups.com, Jann Röder wrote: 3) It provides an entry barrier into the Gnutella Developer game... ... This is solved by PARQ, you only have to obey the retry-after header. What about the upload side? What about accepting QUEUE connect- backs? You should not get QUEUE callbacks if you did not advertise PARQ. You missed the point, which is that a full implementation of PARQ (or remote queueing for that matter) is a non trivial exercise for a new servent developer. ________________________________________________________________________ ________________________________________________________________________ Message: 5 Date: Tue, 10 Jun 2003 13:21:09 -0400 From: "Dave Nicponski" Subject: RE: Re[2]: Re: Unsolicited "QUEUE " messages OK OK OK... Lets look at this as a "Return On Investment" issue... Problems solved by QUEUE type system: 1) User opinion is slightly increased by QUEUE as opposed to BUSY 2) Some behaviors can be controlled or enforced even across vendors (Play nice, or no queue for you! ) 3) "Fairness" - which may or may not be desirable Problems solved by PARQ queue system specifically 4) Short downtime not catastrophic 5) Graceful(?) handling of DHCP IP address changes as far as transfers are concerned 6) A (or a few) issues with firewalled hosts and "ActiveQueueSystem" Does this justify: A) Masssive discussion that may not get anywhere (Is "FAIRNESS" property needed, etc)? B) Time spent to implement and test *another* queue system? Remember that massive adoption of PARQ will act as an additional entry barrier to anyone who wants to write a client, without providing a HUGE benefit (i would say is needed) to justify such a barrier. Personally, I would say a resounding NO to time justified. Better to solve the *REAL* underlying problems, where ROI is going to be orders of magnitude better. -dave- ________________________________________________________________________ ________________________________________________________________________ Message: 6 Date: 10 Jun 2003 17:57:04 GMT From: Raphael_Manfredi@pobox.com Subject: Re: Re[2]: Re: Unsolicited "QUEUE " messages Quoting Dave Nicponski from ml.gnutella.dev-forum: :Personally, I would say a resounding NO to time justified. :Better to solve the *REAL* underlying problems, where ROI is going to be orders :of magnitude better. OK. Don't implement PARQ. Active queueing is enough for you. Otherwise, I agree on the need to solve other real problems, as mentionned by Vinnie and others. It's just that GTKG now happens to have PARQ in, so it's something less that we have to bother at. ________________________________________________________________________ ________________________________________________________________________ Message: 7 Date: 10 Jun 2003 17:59:52 GMT From: Raphael_Manfredi@pobox.com Subject: Re: Unsolicited "QUEUE " messages Quoting Vinnie from ml.gnutella.dev-forum: :You missed the point, which is that a full implementation of PARQ (or :remote queueing for that matter) is a non trivial exercise for a new :servent developer. Sorry, yes. You're right, PARQ is not trivial to implement, and it is about an order of magnitude more complex than simple "Active Queueing" is. Does that mean it's useless? I would not go that far. PARQ solves some problems, but I understand it can appear more as a band aid right now. But as Gnutella improves, it will become an asset. Raphael ________________________________________________________________________ ________________________________________________________________________ Message: 8 Date: Tue, 10 Jun 2003 18:05:33 -0000 From: "Vinnie" Subject: Re: Unsolicited "QUEUE " messages --- In the_gdf@yahoogroups.com, Raphael_Manfredi@p... wrote: You're right, PARQ is not trivial to implement ... Does that mean it's useless? I would not go that far. No, PARQ is not useless, much the same way that a Busy signal from a host which doesn't support queueing is not useless (i.e. almost useless). ________________________________________________________________________ Date: Tue, 10 Jun 2003 17:04:41 -0400 From: "Dave Nicponski" Subject: RE: Re[2]: Re: Unsolicited "QUEUE " messages [QUOTE] Why not have fairness as an objective? [/QUOTE] Why have it? An objective for its' own sake is worthless. Noone has yet to provide a good, realistic reason why it is necessary. Remember, fairness doesn't change the SUPPLY RATE. All it makes sure (apparently, by this definition) is that EVERYBODYS transfers sucks equally much. Now, I can tolerate the few transfers I make which NEVER COMPLETE, but ONLY because of the few (or several) that are MASSIVELY SUCCESSFUL. Take away the good (massively successfull) to eliminate the bad(never complete) and replace them all with something like (All transfers take hours, days, weeks, or months minimum) is NOT appealing to me! I will make a more formal mathematical argument later, when i am "off the clock" [QUOTE] I would not want to use an unfair p2p system. [/QUOTE] So don't. No one is forcing you to. Just don't come complaining back when the ETA for an average file begins MONOTONICALLY GROWING until it reaches the BREAKING POINT (average user's patience limit to wait for an arbitrary file to download has been reached) which will prompt him to LEAVE THE NETWORK. Yes, I am saying this with a straight face, and no I am not paranoid. Again, this is a DIRECT RESULT of the fact that we have DEMAND exceeding SUPPLY. Maybe I can make this EVEN SIMPLER, using an example that NOONE on this panel can POSSIBLY claim isn't appropriate, and everyone has experience with! (Hopefully this example is SOOO simple and accurate that it cannot be reasonably questioned) Pretend that your (BUFFERED!) outgoing TCP/IP pipeline speed is 100KBps. Pretend that your TCP stack has an internal 100KB buffer... I would like to send data out at 150KBps. This is **THE MOST PERFECT ANALOGY** I can come up with here... SUPPLY: 100KBps & 100KB buffer DEMAND: 200KBps Now, the first 1/10th of a second, I want to send 1/10th of 200KB, or 20KB. In this time, only 10KB can physically be sent. The other 10KB is put in a buffer (active QUEUE slot)waiting to be serviced... DISCRETE TIME STEP 1/10: Sent: 10KB, Buffered: 10KB, Lost: NONE DISCRETE TIME STEP 2/10: Sent: 20KB, Buffered: 20KB, Lost: NONE DISCRETE TIME STEP 3/10: Sent: 30KB, Buffered: 30KB, Lost: NONE ...And so one... DISCRETE TIME STEP 10/10 (1 second): Sent: 100KB, Buffered: 100KB, Lost: NONE <== At this point, our outgoing buffer is full DISCRETE TIME STEP 11/10: Sent: 110KB, Buffered: 100KB, Lost: 10KB <== We begin losing packets and have to retry later (BUSY file xfer) DISCRETE TIME STEP 12/10: Sent: 120KB, Buffered: 100KB, Lost: 20KB <== And here it becomes obvious that the situation is getting worse, not better... BUFFERING (DATA QUEUE slots) did NOT help at all! Instead, now there is a DELAY on EVERY BYTE i want to send! It must wait for the other 100KB in buffer to send first... In response to buffer filling up, we may (somewhat reasonably, apparently, based upon comments here) assume that the "PROPER" response is to increase buffer (MORE QUEUE SLOTS! So many, in fact that "IN PRACTICE THEY NEVER FILL UP" ) So we start over, with a MUCH bigger buffer (like PARQs MUCH bigger QUEUE)... Same starting conditions, buffer size of 1GB... DISCRETE TIME STEP 1/10: Sent: 10KB, Buffered: 10KB, Lost: NONE DISCRETE TIME STEP 2/10: Sent: 10KB, Buffered: 10KB, Lost: NONE ...So far, the same... DISCRETE TIME STEP 10/10: Sent: 100KB, Buffered: 100KB, Lost: NONE <==Still the same as before... DISCRETE TIME STEP 11/10: Sent: 110KB, Buffered: 110KB, Lost: NONE DISCRETE TIME STEP 12/10: Sent: 110KB, Buffered: 110KB, Lost: NONE DISCRETE TIME STEP 2000/10: (200 seconds later) Sent: 2000KB, Buffered: 2000KB, Lost: NONE <==Still none lost... BUT: Notice, now, that the **AVERAGE WAIT TIME TO SEND A BYTE OF DATA** has begone to **MONOTONICALLY INCREASE**!!! It also will not stop increasing until we fill our *much expanded* buffer. Every additional bytes sent at this point COMPOUNDS the problem of ever-increasing wait times!!! EGADS! This as a DIRECT RESULT of the "FAIRNESS" desire. So, since "ARBITRARY FILE" wait times will ONLY increase with this "FAIRNESS" system, waits get longer and longer and longer and... When does the madness stop? Glad you asked, here's when: Take all users of Gnutella, U. Ask each of them how many minutes M at most they would be willing to wait for an average file to download, before assuming that "This program/network/whatever sucks!" and go to Kazaa. Then SIGMA(M)/U = average user "FedUp with delay" time T. When the NETWORK WIDE delay for an ARBITRARY file exceeds T, then we reach the natrual conclusion to this runaway scenario. At this point, a steady stream of users will leave, REDUCING (hopefully) only the DEMAND without removing the SUPPLY to the network. Then, either: 1) Steady state of new users, people leaving, and the *ABSOLUTE WORST POSSIBLE WAIT TIME* for files OR 2) Users who leave are the SUPPLY, not the DEMAND, and the network dies. Are my conslusions Draconion? YES Are they Justified? ***YES*** *Quod Erat Demonstrandum* [QUOTE] Why you don't remove the upload queue in Bearshare? You are forced to maintain it for downloading, but nobody (you say) has the right to be queued in your servant. Do the default Bearshare queue of 0 length. Maybe others will follow your example when they see the advantages. My 18 year old brother realizes this is TheWayThingsWork(tm) and tries to make the most of it, using the "Its Not Fair" principle to his advantage, when he can. Okay, you recommend I try to abuse Gnutella as long as I can hide it from you? Are you simply making a "golpe de efecto" or you really believe I should abuse everything I can? Because I see many unfairness daily, but also don't try to promote it. Quite the contrary. [/QUOTE] I am not saying that you should "abuse abuse abuse, as long as I cannot tell"... I am saying that QUEUING combined with this "FAIRNESS" concept (as defined previously) is INHERANTLY DETRIMENTAL TO GNUTELLA'S HEALTH. [QUOTE] I got news for ya: LIFE ISNT FAIR! NOR SHOULD IT BE! I'm glad to be in another neighborhood ;-) [/QUOTE] So it (life) is fair where you live? Be prepared for the massive migration of people into your locale... =) [QUOTE from Raph] But stop shooting at queueing systems, and to PARQ in particular. I know PARQ is not going to solve the supply shortage, but it solves many problems: fairness, hammering, IP changes and other brutal disconnects. [/QUOTE] NO! As long as I feel that the natural conclusion of "FAIR QUEUES" is the rapid destruction of Gnutella, I am going to rant and rave as much as necessary to prevent this! [QUOTE from ] So, to be clear, you just say that if nobody were implementing queues, we would be *exactly* equal than with queues? Please confirm that. That's what I understand from your phrase. [/QUOTE] I believe that the concepts of "FAIRNESS", "FIFO ORDER OF TRANSFERS", "TRANSFER/QUEUE PERSISTANCE ACROSS LAUNCHES", and the protection of the longterm health of Gnutella are MUTUALLY ESCLUSIVE! At least, all attempts to address this are currently... I'll shut up now, and let you all parse this... ________________________________________________________________________ ________________________________________________________________________ Message: 15 Date: Tue, 10 Jun 2003 23:41:09 +0200 From: "Philippe Verdy" Subject: Re: Re[2]: Re: Unsolicited "QUEUE " messages From: "Dave Nicponski" I believe that the concepts of "FAIRNESS", "FIFO ORDER OF TRANSFERS", "TRANSFER/QUEUE PERSISTANCE ACROSS LAUNCHES", and the protection of the longterm health of Gnutella are MUTUALLY ESCLUSIVE! Despite I agree with your argument that the main problem of demand exceeding supplies is the real problem that PARQ will not solve, I still think that PARQ will have positive impact when chunked transfers will be more widely used, as no one will be allowed to monopolize a upload slot for extensive time (with the current high risk that finally that downloading user does not reshare the content he downloaded). Let's implement a scheme in which all downloading users will share the fragments of files they are currently downloading, by caching contents and acting as proxies at least as long as they are downloading the file, and we will greatly increase the supply. Then PARQ will become interesting to load balance the many downloaders of fragments, with also the help of the mesh to find new locations. But please, Dave, stop shouting (with uppercase) ! Gnutella can improve simultaneously in several distinct areas, but each improvement alone will not resolve all the problems. If distinct vendors want to work on some area, it can do so according to its own measurements of the network state, and its development strategy. As long as each improvement is discussed to be interoperable and not cause too much compatibility problem with others (including those that will implement the feature one day, but will not do it immediately), there's some place for everyone, and distinct approaches and experimentations, something that a completely unified network using the same program would not allow... Thanks. --Philippe. ________________________________________________________________________ Date: Wed, 11 Jun 2003 00:03:38 +0200 From: "Philippe Verdy" Subject: Re: Re: Unsolicited "QUEUE " messages From: "Raphael Manfredi" The only downside to that is that you might not be able to contact the server if you don't handle QUEUE, either because its IP has changed or because it is firewalled, and the push route was long lost. Don't think that in terms of "only downside": 1) Usage of firewalls is a reality today(that only PUSHed messages can adress, possibly helped with push proxies). 2) Also the changing dynamic IP address is also a reality today. Both are participating to the fact that the demand now excessively larger than the supply. A "fair" queuing system will only be fair if it also works with firewalled servents. Else you'll simply exclude them from using Gnutella and have any chance of downlading something, simply because they cannot receive the callback connection. What is missing in PARQ is the ability to send the callback notification via existing Gnutella connections. If there's something to improve, it's the stability and recoverability of PUSH routes, so that firewalled servents and servents with changing dynamic IP addresses can be located again on the network. Also PUSH routes should be improved to use shorter relaying paths (once again to improve its stability). If someone could create a advertize/search mechanism to recover broken PUSH routes (with PUSH route servers?), we would greatly improve the connections of firewalled servents, and thus solve a lot of the supply shortage for available upload slots... Couldn't there exist some Web services hosted on non firewalled servents or traditional web servers to help maintain the push routes (but not to proxy the downloads, or to act as file indexers), and thus act only as host locator systems ? ________________________________________________________________________ ________________________________________________________________________ Message: 18 Date: 10 Jun 2003 22:21:18 GMT From: Raphael_Manfredi@pobox.com Subject: Re: Re[2]: Re: Unsolicited "QUEUE " messages Quoting Dave Nicponski from ml.gnutella.dev-forum: :I'll shut up now, and let you all parse this... So what do you suggest we do? Go back to a system where everyone has to retry every 60 seconds exactly to both avoid being banned and seeing the slots it wants taken by someone else? How do you retry when the host is firewalled and your push route is lost? How do you retry when the server's IP changes and your Gnutella horizon does not let you see the new server. Will you requery every time a source dies from your set of known IPs or do you trust the download mesh? It's good to emit critics, and I wish you'd have emitted those critics back when I published the PARQ specs, almost a year ago. But you understand that failing to propose an alternative is not going to buy my vote here, don't you? It's true that slot #68 in my large queue has an ETA of 14 days, at my current upload rate. What would the ETA of that host be without queues, knowing that I have only 3 slots and get many concurrent requests? If you show me a better system, I'll buy it immediately. For some definition of "better" that I will unfortunately not explicit right now, because I don't know yet what it means. Raphael ________________________________________________________________________ Date: Wed, 11 Jun 2003 00:59:39 -0000 From: "Did" Subject: Re: Unsolicited "QUEUE " messages --- In the_gdf@yahoogroups.com, "Dave Nicponski" wrote: I got news for ya: LIFE ISNT FAIR! NOR SHOULD IT BE! If it should be, evolution would not require population turnover, and everyone would get to procreate equally. Yet, I don't see you holding up a picket sign saying "Sex rates are unfair, it should be first come first serve..." I think that's more of a "First served, first come" system ;-D Sorry, I'm in an odd mood. ________________________________________________________________________ ________________________________________________________________________ Message: 2 Date: Tue, 10 Jun 2003 20:23:13 -0700 From: Jay Heyl Subject: RE: Re: Unsolicited "QUEUE " messages At 10:11 AM 6/10/2003 -0400, you wrote: However, if we (Gnutella) cannot satisfy the rate of (content) demand now, how is indefinately queuing demand up going to help? Because, in reality, demand does NOT queue up indefinitely. Downloads are completed by other clients. Users get tired of waiting and log off. Whatever the reason, my observations are that a queue of sufficient, non-infinite size can handle the demands on a single client. [quote] Given that we all know queues work quite well in the physical world and also have extensive application in the digital world, I respectfully suggest that the burden of proof that queues do NOT work should lie with those trying to argue the negative. Hand-waving arguments and simplistic real world analogies should not be taken as proof. [/quote] I truly hope that you are not referring to my post. That was the result of observation and repeated hypothesis, disproval, rinse, repeat. It was also highly influenced by watching IRL people here on Lincoln Road (popular social spot) crowding in, on, and around night clubs and other social hotspots. I was referring to something quoted by Vinnie in one of his replies and, I believe, attributed to you. I'm sorry, but I don't believe any analogy to night clubs and social hotspots is appropriate to the topic at hand. They are particularly inappropriate when you represent the queue by the vestibule of a building. Vestibules are typically small and are necessarily limited in size. Upload queues can be as large as is needed. Your analogy certainly doesn't forbid the use of a large queue, but it does frame the discussion with a prejudice toward queues that are fairly small. A more appropriate analogy would be the post office or, as you mention later on, the DMV, where there are limited opportunities for service and an apparently unlimited opportunity to wait in line. [quote] Currently, all the major players seem to be supporting upload queues. [/quote] This does not imply that queues are good or not. If you took the time to read all my reasoning, it is obvious why every now implements that queuing system. To do otherwise would be foolish! (Follow the link to my posts, and look around for the terms "VIP pass" to understand why this is)... And if you had taken the time to read my message with the goal of understanding what I was trying to say rather than looking for phrases you could quote out of context with the goal of making me look foolish, you would have realized the sentence above about all the major players supporting queues was part of a larger construct reporting that, despite what you seem to be contending to the contrary, my queues have not filled to (current) capacity even though all the major clients now support queueing. [quote] I've even seen some Morpheus clients in my upload queue recently. With almost all of the gnutella world supporting upload queues, I haven't seen the size of my queues exploding and the file transfers are happening in an orderly manner. [/quote] And here you are wrong again! Except, that not only are you wrong, you are **FABRICATING EVIDENCE**! You are stating OPINION as if it were FACT!. Where exactly am I wrong? Where exactly is there OPINION in what was quoted above? I said I've seen Morpheus clients in my upload queue. This is a fact. I have seen them. I said almost all the gnutella world is supporting upload queues. BearShare, LimeWire, Shareaza, Gnucleus, gtk-gnutella, and, apparently now Morpheus, support upload queues. I think that's most of the gnutella world. (My apologies if I've left someone out.) I said I haven't seen the size of my queues exploding. Again, this is an observed fact on my system. I said file transfers are happening in an orderly manner. Again, this is an observed fact on my system. Where am I wrong in any of these statements? You accused me of fabricating evidence. Please show me exactly where I did this. If you can't, I expect an apology. WE have real data, hard and fast numbers that we are steadily collecting, not just "opinion" about the state of things. Vinnie gave you a teeny sample of that, with Downloads/Uplodas info. Queues aren't filling? Yeah right! Get real.... If you set your queue sizes small enough, sure they'll fill up. From what you've said here and your use of the vestibule to represent the queue in your analogy, I can't help but think you're getting stuck on the idea that queues have to be some relatively small size. They don't. They clearly have to be bounded, and a rational discussion of reasonable, practical bounds would probably be a good idea, but they do not have to be small. There is a plethora of cases where queues do not really "work" as far as I am concerned. Do you consider the DMV to be "working" when it takes you 4 hours to register your car? Four hours of wasted time, where you have to sit there doing **NOTHING ELSE**?? Of course not! Its broken! I submit that there's nothing whatsoever wrong with the queue at the DMV. The queue works just fine. You position yourself at the end of the queue. You move in a more or less orderly manner toward the front of the queue. You eventually make it to the top of the queue and get served. The queue has done exactly what it's supposed to do. What's broken at the DMV is that demand far exceeds supply. The queue simply brings order to what would otherwise be chaos in that situation. Would you prefer that it was a free-for-all and whoever managed to push and shove their way to the counter was the one to get served? Gnutella, and file sharing in general, shares at least that characteristic with the DMV. Demand far exceeds supply. So, there is a choice to be made. Would you prefer an environment where the strong or the lucky win out, or one where there's at least an attempt to bring some order to the chaos? I should also add that this doesn't have to be an all-or-nothing situation. I recently experimented with a "queue" that I dubbed the Hit & Run queue. This queue was set up to allow one upload slot and zero entries in the queue. The idea is to provide some of that old survival-of-the-fittest-and-luckiest aspect of the pre-queue days, while still allowing for the more genteel approach of waiting on line like most civilized people prefer. It's still too early to tell whether this "queue" will do anything useful. -- Jay ________________________________________________________________________ ________________________________________________________________________ Message: 3 Date: Tue, 10 Jun 2003 23:41:11 -0400 From: "Sam Berlin" Subject: RE: Re: Unsolicited "QUEUE " messages For those who'd like to look at data, the newer version of LimeWire offers detailed uploading statistics. We generally see a little over half of the HTTP GET requests return a busy response. I suspect that the number significantly rises with larger files and more popular content. In my opinion, that's a lot of needless traffic. Thanks, Sam -----Original Message----- From: Jay Heyl [mailto:jay@heyl.org] Sent: Tuesday, June 10, 2003 11:23 PM To: the_gdf@yahoogroups.com Subject: RE: [the_gdf] Re: Unsolicited "QUEUE " messages At 10:11 AM 6/10/2003 -0400, you wrote: However, if we (Gnutella) cannot satisfy the rate of (content) demand now, how is indefinately queuing demand up going to help? Because, in reality, demand does NOT queue up indefinitely. Downloads are completed by other clients. Users get tired of waiting and log off. Whatever the reason, my observations are that a queue of sufficient, non-infinite size can handle the demands on a single client. [quote] Given that we all know queues work quite well in the physical world and also have extensive application in the digital world, I respectfully suggest that the burden of proof that queues do NOT work should lie with those trying to argue the negative. Hand-waving arguments and simplistic real world analogies should not be taken as proof. [/quote] I truly hope that you are not referring to my post. That was the result of observation and repeated hypothesis, disproval, rinse, repeat. It was also highly influenced by watching IRL people here on Lincoln Road (popular social spot) crowding in, on, and around night clubs and other social hotspots. I was referring to something quoted by Vinnie in one of his replies and, I believe, attributed to you. I'm sorry, but I don't believe any analogy to night clubs and social hotspots is appropriate to the topic at hand. They are particularly inappropriate when you represent the queue by the vestibule of a building. Vestibules are typically small and are necessarily limited in size. Upload queues can be as large as is needed. Your analogy certainly doesn't forbid the use of a large queue, but it does frame the discussion with a prejudice toward queues that are fairly small. A more appropriate analogy would be the post office or, as you mention later on, the DMV, where there are limited opportunities for service and an apparently unlimited opportunity to wait in line. [quote] Currently, all the major players seem to be supporting upload queues. [/quote] This does not imply that queues are good or not. If you took the time to read all my reasoning, it is obvious why every now implements that queuing system. To do otherwise would be foolish! (Follow the link to my posts, and look around for the terms "VIP pass" to understand why this is)... And if you had taken the time to read my message with the goal of understanding what I was trying to say rather than looking for phrases you could quote out of context with the goal of making me look foolish, you would have realized the sentence above about all the major players supporting queues was part of a larger construct reporting that, despite what you seem to be contending to the contrary, my queues have not filled to (current) capacity even though all the major clients now support queueing. [quote] I've even seen some Morpheus clients in my upload queue recently. With almost all of the gnutella world supporting upload queues, I haven't seen the size of my queues exploding and the file transfers are happening in an orderly manner. [/quote] And here you are wrong again! Except, that not only are you wrong, you are **FABRICATING EVIDENCE**! You are stating OPINION as if it were FACT!. Where exactly am I wrong? Where exactly is there OPINION in what was quoted above? I said I've seen Morpheus clients in my upload queue. This is a fact. I have seen them. I said almost all the gnutella world is supporting upload queues. BearShare, LimeWire, Shareaza, Gnucleus, gtk-gnutella, and, apparently now Morpheus, support upload queues. I think that's most of the gnutella world. (My apologies if I've left someone out.) I said I haven't seen the size of my queues exploding. Again, this is an observed fact on my system. I said file transfers are happening in an orderly manner. Again, this is an observed fact on my system. Where am I wrong in any of these statements? You accused me of fabricating evidence. Please show me exactly where I did this. If you can't, I expect an apology. WE have real data, hard and fast numbers that we are steadily collecting, not just "opinion" about the state of things. Vinnie gave you a teeny sample of that, with Downloads/Uplodas info. Queues aren't filling? Yeah right! Get real.... If you set your queue sizes small enough, sure they'll fill up. From what you've said here and your use of the vestibule to represent the queue in your analogy, I can't help but think you're getting stuck on the idea that queues have to be some relatively small size. They don't. They clearly have to be bounded, and a rational discussion of reasonable, practical bounds would probably be a good idea, but they do not have to be small. There is a plethora of cases where queues do not really "work" as far as I am concerned. Do you consider the DMV to be "working" when it takes you 4 hours to register your car? Four hours of wasted time, where you have to sit there doing **NOTHING ELSE**?? Of course not! Its broken! I submit that there's nothing whatsoever wrong with the queue at the DMV. The queue works just fine. You position yourself at the end of the queue. You move in a more or less orderly manner toward the front of the queue. You eventually make it to the top of the queue and get served. The queue has done exactly what it's supposed to do. What's broken at the DMV is that demand far exceeds supply. The queue simply brings order to what would otherwise be chaos in that situation. Would you prefer that it was a free-for-all and whoever managed to push and shove their way to the counter was the one to get served? Gnutella, and file sharing in general, shares at least that characteristic with the DMV. Demand far exceeds supply. So, there is a choice to be made. Would you prefer an environment where the strong or the lucky win out, or one where there's at least an attempt to bring some order to the chaos? I should also add that this doesn't have to be an all-or-nothing situation. I recently experimented with a "queue" that I dubbed the Hit & Run queue. This queue was set up to allow one upload slot and zero entries in the queue. The idea is to provide some of that old survival-of-the-fittest-and-luckiest aspect of the pre-queue days, while still allowing for the more genteel approach of waiting on line like most civilized people prefer. It's still too early to tell whether this "queue" will do anything useful. -- Jay ________________________________________________________________________ Date: Wed, 11 Jun 2003 09:35:43 -0400 From: "Dave Nicponski" Subject: RE: Re: Re[2]: Re: Unsolicited "QUEUE " messages Sorry, I didnt see the PARQ specs a year ago, or I would have mentioned this then. I'm still only a year into the [QUOTE] If you show me a better system, I'll buy it immediately. [QUOTE] I will hold you to that. =) I am working on this problem, rest assurred. [QUOTE] For some definition of "better" that I will unfortunately not explicit right now, because I don't know yet what it means. Raphael [/QUOTE] Ack... only thinkg worse than a moving target is one which isn't yet defined... heh But, I expect that that which would seem "Better" to me/Joe average-user/you/whoever is fundamentally the same, so no problem. OK. -dave- ________________________________________________________________________ Date: Wed, 11 Jun 2003 09:46:34 -0400 From: "Dave Nicponski" Subject: RE: Re: Unsolicited "QUEUE " messages [QUOTE] --- In the_gdf@yahoogroups.com, "Dave Nicponski" wrote: I got news for ya: LIFE ISNT FAIR! NOR SHOULD IT BE! If it should be, evolution would not require population turnover, and everyone would get to procreate equally. Yet, I don't see you holding up a picket sign saying "Sex rates are unfair, it should be first come first serve..." I think that's more of a "First served, first come" system ;-D Sorry, I'm in an odd mood. [/QUOTE] +1 Funny ROFL... -dave- ________________________________________________________________________ ________________________________________________________________________ Message: 6 Date: Wed, 11 Jun 2003 10:00:49 -0400 From: "Dave Nicponski" Subject: RE: Re: Unsolicited "QUEUE " messages [QUOTE] I was referring to something quoted by Vinnie in one of his replies and, I believe, attributed to you. I'm sorry, but I don't believe any analogy to night clubs and social hotspots is appropriate to the topic at hand. [/QUOTE] So, real world examples of Queues that are in operation and accepted by general public as not being "Too abusive" or whatever have nothing interesting to add to the scenario? Thats fairly limited. But, believeing it or not doesn't change my conclusion. To quote "Matrix 2", My beliefs do not require you to. =) [QUOTE] They are particularly inappropriate when you represent the queue by the vestibule of a building. [/QUOTE] So, an analogy of a queue to a queue is inappropriate? Hmm... [QUOTE] Vestibules are typically small and are necessarily limited in size. [/QUOTE] Like so-called "Active Queuing"? Hmm.. [QUOTE] Upload queues can be as large as is needed. Your analogy certainly doesn't forbid the use of a large queue, but it does frame the discussion with a prejudice toward queues that are fairly small. [/QUOTE] Ahh, I see you haven't bothered to FINISH reading the arguments against queuing, specifically the one why large, durable, so-called "FAIR" queue isn't going to work either. Look again. Just because You didn't read it doesn't make it less valid. =) [QUOTE[ A more appropriate analogy would be the post office or, as you mention later on, the DMV, where there are limited opportunities for service and an apparently unlimited opportunity to wait in line. [/QUOTE] Actually, you are wrong about this. This kind of queue (post office, etc) has other factors working in its advantage that cause it to be workable. In fact, most IRL queues (for people) have the EXACT same "benefit" that lets them work properly. ( Check out my more exact analogy, in the paper on LONG queues, with TCP buffering, for an exact analogy. ) Even the vestibule scenario had this problem in the analogy, but it was only to help you visualize that the underlying problem wasn't addressed by a queue. Specifically, They can enforce upon you the following condition(s), which cannot easily be transferred to Gnutella: 1) The act of offering you a queue slot (a place in line) places an immediate, unshakable BAN on other queues. This prevents you from continuing to pile up outstanding "Consume Resource" commands. 2) At 6:00, the post office closes its door (NO MORE DEMAND!!! =) yet the employees will stick around to service the remaining queued Demand. This does *not* transfer to gnutella in any easy way that I can see, unless you force the user to remain online after they would wish to leave. Actually, we are discussing potential solutions to thi problem. Hopefully we will stuble onto something really useful. There are also a (3) and (4) that are directly responsible for why this analogy doesn't work (except as a concept analogy for the underlying problem, which your post office argument didn't change, and even enforces, same problem of supply and demand!) -dave- ________________________________________________________________________ ________________________________________________________________________ Message: 7 Date: Wed, 11 Jun 2003 10:04:50 -0400 From: "Dave Nicponski" Subject: RE: Re: Unsolicited "QUEUE " messages [QUOTE] What's broken at the DMV is that demand far exceeds supply. [/QUOTE] Exactly as in Gnutella today. [QUOTE] The queue simply brings order to what would otherwise be chaos in that situation. Would you prefer that it was a free-for-all and whoever managed to push and shove their way to the counter was the one to get served? [/QUOTE] Real world shoving == real world bruises, so no, of course not. But, the properties of the Queuing system that provide the advantage of bringing order and allowing it to work simply do not carry over into the digital realm (at least as provided for so far) and I don't see any robust way of solving this problem at a QUEUE level. [QUOTE] Gnutella, and file sharing in general, shares at least that characteristic with the DMV. Demand far exceeds supply. So, there is a choice to be made. Would you prefer an environment where the strong or the lucky win out, or one where there's at least an attempt to bring some order to the chaos? I should also add that this doesn't have to be an all-or-nothing situation. I recently experimented with a "queue" that I dubbed the Hit & Run queue. This queue was set up to allow one upload slot and zero entries in the queue. The idea is to provide some of that old survival-of-the-fittest-and-luckiest aspect of the pre-queue days, while still allowing for the more genteel approach of waiting on line like most civilized people prefer. It's still too early to tell whether this "queue" will do anything useful. -- Jay [/QUOTE] How is "Hit&Run" differant that current "Active Queuing" with a queue of 1? -dave- ________________________________________________________________________ ________________________________________________________________________ Message: 8 Date: Wed, 11 Jun 2003 10:06:04 -0400 From: "Dave Nicponski" Subject: RE: Re: Unsolicited "QUEUE " messages This happens today with Active queuing, and (if i recall) with PARQ as well. [QUOTE] It would probably make sense for the queue polling window (sorry if I'm not using proper terminology here) to be somewhat adaptive to a client's position within a queue. If a client is at position 500 in a queue with a minimum download size of 20MB, there's clearly no point in that client checking back in every two minutes. Twenty, maybe even thirty, minutes would be more reasonable. As the request moves closer to the top of the queue, reduce the polling window callback time. This won't eliminate the problem, but it will certainly reduce it to a great extent. -- Jay [/QUOTE] ________________________________________________________________________ Date: Wed, 11 Jun 2003 18:56:02 -0000 From: "jim_taylor_stockholm" Subject: Re: Unsolicited "QUEUE " messages --- In the_gdf@yahoogroups.com, "Dave Nicponski" wrote: Ahh, I see you haven't bothered to FINISH reading the arguments against queuing, specifically the one why large, durable, so- called "FAIR" queue isn't going to work either. Look again. Just because You didn't read it doesn't make it less valid. =) I have read them all and I think mosteo, Raphael et al have more than dealt with the claims that implementing PARQ will somehow harm uploads and not deal with high demand more fairly and efficiently than the short "Active" queuing systems in place today. Instead of real world examples or fantasy Post Offices try considering eMule again. I have heard many people say that it doesn't work. Well here's the first thing you should learn from this 1,000,000 user network - it DOES work. Everybody seems sure that there is a magic bullet for PFS and BitTorrent's Tracker protocols may be it, but until someone has transformed Gnutella to use these new protocols we're stuck with pure P2P intelligence and at the moment the most intelligent thing to do with high demand is PARQ. ________________________________________________________________________ Date: Wed, 11 Jun 2003 15:08:57 -0400 From: "Dave Nicponski" Subject: RE: Re: Unsolicited "QUEUE " messages You can make fun of the "concept analogies" i used, or you can extract the CONCEPT from them which i was trying to use to illustrate that the underlying problem is being overlooked. Even if you don't find that useful or helpful at all, how do you answer (what i consider) the most convincing evidence at all, which is the completely equivelent outgoing data buffering case? If you want to try to poke holes at something, use THAT one, not the "fantasy post office", as you say. It is intended to be the "equivalent" case, and i believe that it is completely analogous and will stand up to all your scrutiny. Maybe not, though. -dave- [QUOTE] --- In the_gdf@yahoogroups.com, "Dave Nicponski" wrote: Ahh, I see you haven't bothered to FINISH reading the arguments against queuing, specifically the one why large, durable, so- called "FAIR" queue isn't going to work either. Look again. Just because You didn't read it doesn't make it less valid. =) I have read them all and I think mosteo, Raphael et al have more than dealt with the claims that implementing PARQ will somehow harm uploads and not deal with high demand more fairly and efficiently than the short "Active" queuing systems in place today. Instead of real world examples or fantasy Post Offices try considering eMule again. I have heard many people say that it doesn't work. Well here's the first thing you should learn from this 1,000,000 user network - it DOES work. Everybody seems sure that there is a magic bullet for PFS and BitTorrent's Tracker protocols may be it, but until someone has transformed Gnutella to use these new protocols we're stuck with pure P2P intelligence and at the moment the most intelligent thing to do with high demand is PARQ. [/QUOTE] ________________________________________________________________________ Date: Wed, 11 Jun 2003 22:41:14 -0000 From: "jim_taylor_stockholm" Subject: Re: Unsolicited "QUEUE " messages OK so why is PARQ "fairer," well, when a peer decides to dedicate a few hours, or days, to downloading a file I think it is "just" that his FIFO (or equivalent "fair") rights are respected no matter how long the queue is. You are only depriving the rest of your users of these rights if you shorten your queues. The extrapolation you neglect to include in your example for Active Queuing (the current system): DISCRETE TIME STEP 2000/10: (200 1/10 seconds later) Sent: 2000KB, Buffered: 100KB, Lost: 1900KB <== ~50% LOST! (as expected from initial specs :-/).. ..which means there is a massive amount of unmanaged (Lost!) demand flying round the network, which brings me to the second point I made, efficiency. PARQ should be able to precisely schedule upload slots (mosteo's determinism again), especially with time based slot rotation. The best Active Queuing can do in a congested situation is back off exponentially. This would undoubtedly be less efficient than a specifically timed or passively triggered mechanism and it does not have PARQ's benefits: "Legacy" and "Remanence". Are my conslusions Draconion? YES Are they Justified? ***YES*** I love your pretty stars Dave, they make me smile. But draconian well you're shooting yourself in the foot there, or being brave, grrr. I think I see your fear though, that if people see how long they have to wait, they won't wait. eMule is testimony to the opposite. Really - 'nuff said. Now, not even the capacity offered by 1,000,000 users give eMulers' the ability to download things as fast as BitTorrent using PFS alone, so watch the space of the first person to distribute the BT algorithms... maybe, if BT scales. ________________________________________________________________________ Date: Thu, 12 Jun 2003 00:13:23 -0700 From: Jay Heyl Subject: RE: Re[2]: Re: Unsolicited "QUEUE " messages At 05:04 PM 6/10/2003 -0400, you wrote: This is **THE MOST PERFECT ANALOGY** I can come up with here... SUPPLY: 100KBps & 100KB buffer DEMAND: 200KBps I quote the above simply to provide reference. It is not intended to represent the entirety of the analogy, which was quite lengthy and detailed. What follows addresses the entire analysis, not just the portion quoted above. I believe the fundamental problem with this analysis is an assumption of infinite demand for the resources of every user who is sharing files. No one is going to deny that, overall, demand is much greater than supply. That's a given. But it does not necessarily follow that demand exceeds supply at every given point in time or for every user. There will be points in time where, for any single user, supply will exceed demand and the queue will shrink. There may even be rare points in time where the queue will empty. The analogy also assumes a constant, inelastic demand. (I don't want to pick on the analogy too much, but I do think it's warranted to point out where the analogy differs from the real situation.) Demand is not constant, it varies by time of day and probably a dozen other variables, and, while I have no definite proof of this, common sense tells me demand is elastic. (If the line at the post office is too long today, I'll try again tomorrow morning. If I can't download that hot new file tonight, I'll try again tomorrow.) If this was not the case, if the assumptions about demand in the analysis were correct, everyone's queues would already be steadily growing. Not just slowly changing average load as more clients offer queueing, but steadily and noticeably growing to the maximum allowed queue size. After a week or two of being online 24/7, anyone offering reasonably popular files should see their queues filled to capacity all the time. I haven't seen this. I haven't heard of anyone else complaining about it. I haven't noticed any increase in the number of people complaining that it's hard to get downloads to complete. I've been sharing files for the last month or so on the eDonkey network which, I'm told, has in excess of one million users, a large percentage of whom stay online for extended periods of time. If demand were truly constant, inelastic, and essentially infinite, I should be seeing my eDonkey queue grow continually larger. I currently have it set to allow 2000 entries in the queue. The most I've ever seen in the queue is a bit over 500. The majority of the time it hovers between 150 and 200 entries. At this moment there are 165 entries in that queue. (And, bear in mind, this is a network where the clients queue up requests with EVERY node that has the desired file. It's just about the worst case for queue abuse.) My eDonkey queue is not growing out of control. The queues I have that are used by gnutella almost never grow beyond 20 entries. ________________________________________________________________________ ________________________________________________________________________ Message: 2 Date: Thu, 12 Jun 2003 09:58:46 -0000 From: "jim_taylor_stockholm" Subject: Re: Unsolicited "QUEUE " messages --- In the_gdf@yahoogroups.com, Jay Heyl wrote: At 05:04 PM 6/10/2003 -0400, you wrote: This is **THE MOST PERFECT ANALOGY** I can come up with here... SUPPLY: 100KBps & 100KB buffer DEMAND: 200KBps ... But it does not necessarily follow that demand exceeds supply at every given point in time or for every user. There will be points in time where, for any single user, supply will exceed demand and the queue will shrink. There may even be rare points in time where the queue will empty. Very good point Jay, **THE MOST PERFECT ANALOGY** does indeed imply that queues only ever fill up. As you say, we all agree that queuing will not solve the demand/supply problem and Dave's analogy clearly shows us that you have to wait longer the further back you are in the queue, but as I said in my post PARQ does indeed provide fairness in congested circumstances, using long queues, fairness in times of network frailty, using persistent queues and improved determinism where you could be left with none using the current system. ________________________________________________________________________ ________________________________________________________________________ Message: 3 Date: Thu, 12 Jun 2003 10:04:24 -0000 From: "Did" Subject: Re: Unsolicited "QUEUE " messages --- In the_gdf@yahoogroups.com, Jay Heyl wrote: I believe the fundamental problem with this analysis is an assumption of infinite demand for the resources of every user who is sharing files. No one is going to deny that, overall, demand is much greater than supply. That's a given. But it does not necessarily follow that demand exceeds supply at every given point in time or for every user. There will be points in time where, for any single user, supply will exceed demand and the queue will shrink. There may even be rare points in time where the queue will empty. Say PARQ is implemented by all, users will be able to participate in more queues at once, maybe even every download they attempt and there are some who like to attempt every result they recieve and then cancel most when one gets going. Then the download mesh would add many more sources to each attempt and all of those would be attempted and queued. Because of this we would then see queue lengths >> number of users, maybe thousands of times longer. But this is not all bad, users cancel nearly all their (queued) downloads as others complete. The 'long' queues advance more quickly than regular queues so wait times are not many months longer than before. Hoorah! Nothing is acheived accept we now use less bandwidth and more memory. On my part I like the benefits of a passive system but not the ridiculously long queues. I wouldn't want to see 'Queued 1261/2000' but I would like to see 'Queued 12/12', I could live with seeing 'Queued'. How about the servent only show the position when less than 20? ________________________________________________________________________ ________________________________________________________________________ Message: 4 Date: Thu, 12 Jun 2003 12:12:02 +0200 From: "Alejandro. R. Mosteo Chagoyen" Subject: Re: Re: Unsolicited "QUEUE " messages (...) I wouldn't want to see 'Queued 1261/2000' but I would like to see 'Queued 12/12', I could live with seeing 'Queued'. How about the servent only show the position when less than 20? Now *that* is placebo ;-) ________________________________________________________________________ Date: Thu, 12 Jun 2003 14:46:29 -0000 From: "jim_taylor_stockholm" Subject: Re: Unsolicited "QUEUE " messages --- In the_gdf@yahoogroups.com, "Alejandro. R. Mosteo Chagoyen" wrote: (...) I wouldn't want to see 'Queued 1261/2000' but I would like to see 'Queued 12/12', I could live with seeing 'Queued'. How about the servent only show the position when less than 20? Now *that* is placebo ;-) Exactly mos'. LOL. I'd rather have the real and realistic benefits of PARQ than a wing and a prayer. --- In the_gdf@yahoogroups.com, "Did" wrote: there are some who like to attempt every result they recieve and then cancel most when one gets going. Then the download mesh would add many more sources to each attempt and all of those would be attempted and queued. Because of this we would then see queue lengths >> number of users, maybe thousands of times longer. If you do a broad search and get lots of results they bring back lots of *different* hosts, so the peer that attempts every result will be taking (possibly) thousands of queue places but it would only swell each queue by one or two or whatever the value to which max uploads per unique host is set. It would take thousands of users to behave this way for queue lengths to grow by thousands. ________________________________________________________________________ ________________________________________________________________________ Message: 3 Date: Thu, 12 Jun 2003 17:02:57 +0200 From: "Philippe Verdy" Subject: Re: Re: Unsolicited "QUEUE " messages From: "jim_taylor_stockholm" To: Sent: Thursday, June 12, 2003 4:46 PM Subject: [the_gdf] Re: Unsolicited "QUEUE " messages --- In the_gdf@yahoogroups.com, "Alejandro. R. Mosteo Chagoyen" wrote: (...) I wouldn't want to see 'Queued 1261/2000' but I would like to see 'Queued 12/12', I could live with seeing 'Queued'. How about the servent only show the position when less than 20? Now *that* is placebo ;-) Exactly mos'. LOL. I'd rather have the real and realistic benefits of PARQ than a wing and a prayer. I have exactly the same opinion, I, as a user, would prefer to see my rank progressiely decrease rapidly from 1261/2000 to 1240/2000 etc... instead of waiting for many hours that the message "Queued" changes into something more informational. In fact if I can't wait for this time, I can still see how the ranking evolves, and expect a reasonnable response at some expected time. However, a ranking system will proe beneficial if servents also implements partial file sharing while they are downloading a file, so that they contribute also to the number of alternate sources for the expected file. There are several ways to manage queues, one could manage a priority queue per file, so that all demanded files are uploaded and shared, or a unique upload queue for all files. The first approach would allow rare files that are also more rarely demanded to be served faster, greatly enhancing the distribution of the newest files that don't have a lot of locations or sometimes not any other known location. This would create separate queues for each shared file, and each shared file would then be queued individually independantly of the number of people requesting them. So the indication "Queued X/Y" could be an estimate based on the total of shared files currently requested (independantly of the number of people requesting each of them), and the number of people in the current file queue. ________________________________________________________________________ ________________________________________________________________________ Message: 4 Date: Thu, 12 Jun 2003 17:28:03 +0200 From: "Philippe Verdy" Subject: Re: Re: Unsolicited "QUEUE " messages From: "Philippe Verdy" There are several ways to manage queues, one could manage a priority queue per file, so that all demanded files are uploaded and shared, or a unique upload queue for all files. The first approach would allow rare files that are also more rarely demanded to be served faster, greatly enhancing the distribution of the newest files that don't have a lot of locations or sometimes not any other known location. This would create separate queues for each shared file, and each shared file would then be queued individually independantly of the number of people requesting them. So the indication "Queued X/Y" could be an estimate based on the total of shared files currently requested (independantly of the number of people requesting each of them), and the number of people in the current file queue. I forgot to speak about other possible approaches when managing per-file queues: in order to maximize the number of alternate locations and not favor only the most popular files, one could design each queue so that it will track the number of alternate locations currently known. When a upload finishes, a random selector could allow switch between two approaches when selecting the next file to handle: it could be the next per-file queue in the global queue, or the per-file queue that has the lowest number of alt-locations (this implies two parallel global queues with one entry in each one per demanded file). When this next file to serve is determined, the per-file queue is rotated in the two global queues and reordered and rotated accordingly to their respective policy. The next client to serve is then the first one in the selected per-file queue. This approach would still allow serving the most demanded files (those that have the longest per-file queues) without sacrificing too much the diversity of files available in the network (a bad effect of a single global queue, because a single file in the total of shared files on a host would jeopardize all the upload resources if it's too much "popular" and too new and thus too widely demanded, and that makes too many QueryHits unusable if they are not "popular" i.e. demanded). ________________________________________________________________________ ________________________________________________________________________ Message: 5 Date: Thu, 12 Jun 2003 18:32:13 -0000 From: "jim_taylor_stockholm" Subject: Re: Unsolicited "QUEUE " messages --- In the_gdf@yahoogroups.com, "Philippe Verdy" wrote: This approach would still allow serving the most demanded files (those that have the longest per-file queues) without sacrificing too much the diversity of files available in the network (a bad effect of a single global queue, because a single file in the total of shared files on a host would jeopardize all the upload resources if it's too much "popular" and too new and thus too widely demanded, and that makes too many QueryHits unusable if they are not "popular" i.e. demanded). I agree that there are many ways to configure queues. I have had great *fun* with Shareaza's new queues editor - it is a good feeling for a user to be able to share files the way *they* want to. I personally hope Shareaza implements PARQ because the popularity of my larger files means that it's ED2K queuing implementation is the only protocol able to efficiently queue the number of people that want the files which obviously means that the files are unfortunately not shared on the Gnutella networks. The holy grail of distributing popular files without forgetting the rare-un's is IMHO impossible, but I do think there could be better more efficient PFS systems that might give more capacity to less popular files. Implementing PARQ will certainly help distribution of less popular files because the long queues will ensure your request for the rare file is not forgotten. ________________________________________________________________________ ________________________________________________________________________ Message: 6 Date: Fri, 13 Jun 2003 00:44:42 +0200 From: "Philippe Verdy" Subject: Re: Re: Unsolicited "QUEUE " messages jim_tailor wrote: Implementing PARQ will certainly help distribution of less popular files because the long queues will ensure your request for the rare file is not forgotten. I don't think so: if PARQ is deplyed in a way that all upload servers have now very long queues, it will be nearly impossible to find alternate sources before a long time for a rare file. We can penalize a bit the most popular files that also get the most demand as they certainly have more potential sources in the mesh. But for rare files with unique locations, they will be impossible to transfer because they are immediately placed far away in the queues by the most demanded files. So if the unique source disconnects, the rare unique file will never be uploaded somewhere else, and the downtime for these files will be much higher than for files that are requested and uploaded often. Also, it's impossible to predict the effect of being in a long queue that contains lots of requests for large files, if my demand for the rare file is immediately placed at end of the queue. This file will not be duplicated before long. The most demanded files will not have this problem: their "downtime" is much more smoothed. A demand for those files can stay longer in the queue but still benefit for more alt-locations some of them having shorter queues. If one uploader disconnects, there still remains the rest of the mesh to continue the download, and the total time to wait for those files can be much shorter as one can swarm these sources by placing its demands in multiple queues. This means that the rate of successful transfers for rare files will be small or nil, and things may get even worse when servents will start uploading only small fragments: for a rare file, each fragment will need to be requeued. If a fragment has been transfered, of course it can be shared, but the mesh will not provide alternate locations for the rest of the file, notably if the file is large. I think it's best to boost a little the least popular files. This will not affect much the most demanded ones, but will help provide more diversity to the content available on the Gnet. I would not like to use Gnutella only to be offered the same set of popular files that I have seen many times or that I may already have: so if I browse the host to look for other interesting files for the same subject, I will find rare ones but I will be placed at the same position as files that are the most demanded and have the most important number of alt-locations. So I think that the number of alt-locations discovered for each file should be considered to help boost the files that are less distributed in the Gnet (because downloaders won't be able to attend at multiple queues to download it by fragments). ________________________________________________________________________ ________________________________________________________________________ Message: 7 Date: Fri, 13 Jun 2003 01:13:19 +0200 From: "Philippe Verdy" Subject: Re: Re: Unsolicited "QUEUE " messages I'd like to make an analogy: Consider a large marketing company where business workers all have a lot of documents to duplicate of various sizes. The company has a limited set of photocopiers to duplicate these documents. When someone wants to have its photocopies, it takes a ticket in front of the copier it wants to use. However copiers have different capabilities, and for some large or colored documents only one model can satisfy the demand, but for basic documents such as letters all models are usable. People that have letters to duplicate will take a ticket in each queue. The number of tickets available is assumed to be infinite (this is the case for PARQ which can support extremely long queues), but one cannot take a ticket for a queue if he already has a ticket for another document. But to avoid that the queues stay idle for too long time, a policy limits the number of pages that can be duplicated: when this quotais exceeded, the ticket is taken and gies the right to take a new ticket for the same machine. Now what will happen? If there is no other policy, the people that have letters to duplicate can use all copiers and satisfy their demand in a reasonable time (as if they had waited only once in only one queue) even if they have lots of copies to create. But those people that have large documents to duplicate will only be able to wait at the same single queue for the specific copier. If the number of pages to create is above the threshold, once he has got his quota, he must wait a second time for the same duration in the same queue to continue his task. The total time to wait then becomes N times longer for that person that can wait at a single queue. Suppose that that copier gets out of paper, and needs to be put offline waiting for someone to service it, the worker will need to wait also that this matintenance completes. On the other side, other workers with letters can simply go to all the other copiers and have their work completed without much more delay. Now add a policy, and give some priority to those workers htat have large or color document to duplicate to use the specific model. They now can regain some avantage which will compensate the fact that there's no other machine able to process the document. The impact is that they will experiment a shorter queue on a single machine, than people that can attend simultaneously on several queues to process their copies in parallel on several machines when they gain the first rank oneach of them. The total productivity of the workers in terms of pages duplicated per hour becomes more fair, and each one can do its job in time and send the letters to its customers... How can a queuing system (with limited short queues in active queuing, or infinite queues in PARQ) support this similar policy ? By using per-file queues in which downloaders can take a ticket for that file, and for which the uploading server will collect alternative locations. The more alt-locations is available, the less priority is given to that file. I don't want to promote a all-or-nothing system, but just say that per-file queues can help service rare files better without affecting much the service for popular files. Of course this model will probably not work with active queueing (because one cannot have a lot of per-file queues) but will prove useful when PARQ will be used in addition to PFS and an upload policy that limits the size of fragments delivered to each client. ________________________________________________________________________ ________________________________________________________________________ Message: 8 Date: 13 Jun 2003 06:31:27 GMT From: Raphael_Manfredi@pobox.com Subject: Re: Unsolicited "QUEUE " messages Quoting Philippe Verdy from ml.gnutella.dev-forum: :jim_tailor wrote: :> Implementing PARQ will certainly help distribution of less popular :> files because the long queues will ensure your request for the rare :> file is not forgotten. : :I don't think so: if PARQ is deplyed in a way that all upload servers :have now very long queues, it will be nearly impossible to find alternate :sources before a long time for a rare file. Why do you think so? Since the downloader retries every so and then (20 minutes is the maximum retry delay in current GTKG's implementation), it can exchange the mesh info with the server on a regular basis. How is this making it nearly impossible to find alt sources? Raphael ________________________________________________________________________ ________________________________________________________________________ Message: 9 Date: Fri, 13 Jun 2003 08:59:07 +0200 From: "Alejandro. R. Mosteo Chagoyen" Subject: Re[2]: Re: Unsolicited "QUEUE " messages How can a queuing system (with limited short queues in active queuing, or infinite queues in PARQ) support this similar policy ? By using per-file queues in which downloaders can take a ticket for that file, and for which the uploading server will collect alternative locations. The more alt-locations is available, the less priority is given to that file. I don't want to promote a all-or-nothing system, but just say that per-file queues can help service rare files better without affecting much the service for popular files. If I'm understanding correctly, you are proposing a two level system: One with a queue per file (usually fifo?) and a priority queue of queues, which determines from what queue the next starting upload must be selected. If that's the case, I would note that that's theoretically equivalent to have a single priority queue where slots with same priority are treated in fifo order. Maybe this vision could be more appealing to some. However your model seems to me for now cleaner from a "thinking" perspective, from a practical (implementation) one maybe this second is easier. Another problem that multiple queues have and I've not seen discussed (but which affects for example the latest Shareaza queuing system) is when a request can satisfy the entry condition of two or more queues in the same server. When you split the requests by file size, if they don't overlap, this problem doesn't arise (use however [x,y) intervals :). But let's say you have two queues, one prioritized by "rareness" and another by fifo policy. In that case, instead of choosing only one queue by some reason (precedence, shortness), I think that what must be done is: *) Enqueue each request in every queue that satisfies the entry condition. *) When a request reaches a head and is ready to upload, remove it from the other queues. This ensures optimal wait time for clients and that no queue can be emptied while other has candidate clients. This is my theoretical view, maybe it's implementation detail (you could review queues in a periodical manner and requeue clients if other queues are shorter), but at least is a real problem to not forget about. I'm still thinking on the default queues I want to define in my server, but for now I think on these: (please explain the problems you find in it): *) a fifo queue. *) a shorter file first queue. *) a rarest file first queue. Also, they preempt after 15 minutes of upload or 15 MB sent. This seem reasonable default for everything like music and below, leaving the preemption only for really big files. The multiple-queuing is in place (yes, queues are three times larger, but that only takes a bit more memory and they shorten also thrice as fast :) I see the problem of the "live" (uploading) slots. What's the usual number for a 56k modem user? If it's <3 then some other defaults must be provided (or take Philippe approach and establish a priority for the ready queues). What does Gtk-Gnutella? Minimum a live slot per queue or not? Kind regards. ________________________________________________________________________ ________________________________________________________________________ Message: 10 Date: Fri, 13 Jun 2003 09:13:11 -0000 From: "jim_taylor_stockholm" Subject: Re: Unsolicited "QUEUE " messages --- In the_gdf@yahoogroups.com, "Philippe Verdy" wrote: I'd like to make an analogy: I'd like to avoid more analogies. Like most metaphors they break down at some point and although they are useful for making complex situations more understandable I think the long queue reality is simple enough to deal with directly. Having said that I agree with most of the logic behind your previous post but as I stated I am certainly not sure (is that a Rumsfeld-ism) LOL) of any solutions to the rare file problem, and especially the large rare file problem you mentioned - that's a doozy! :) I certainly do not want to stop you coming up with ideas though Philippe and I feel sure that a long queue gives you more information to work with re. optimizing for rare files than a short queue does. I am certain of PARQ's benefits now though and I hope it's powerful scalable queuing becomes another corner-stone of the Gnutella network. ________________________________________________________________________ Date: Sat, 14 Jun 2003 01:19:49 +0200 From: Arne Bab. Subject: Re: Unsolicited "QUEUE " messages -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 I am certain of PARQ's benefits now though and I hope it's powerful scalable queuing becomes another corner-stone of the Gnutella network. I'm now following this discussion for a while, and I want to add a new point in this discussion: Getting a file instantly. For small files, I like about the Gnutella Network, that I can simply click them, and they are downloaded instantly, or not at all. There is no waiting included. For a large file I'd already have to wait some time for the download to finish, so a queue doesn't bother me. So I like the Idea of a queue for big files, and some simple upload slots for smaller ones. Maybe 1/3 of the slots for larger files using PARQ or something similar (at least one) and the rest as simple upload slots (at least one). To reduce the demand a bit, you could reduce the number of simultaneous downloads,, or let the User do that. I am on a modem, so if 20 dls start at once, I get none of them (all of them break -> hosts appear to be offline, but aren't). The largest number, which still work is three, with a much too great failure rate, so for me I'd need it at two. So simply check only three files-to-be-downloaded at once, standardly (maybe let the user specify this), and don't check any more f-t-b-dd, when there are already three dls running. Simply queue them on the requesters side. So no upload spots are wasted on very slow dls. I am no programmer, so this is simply a Users opinion. My Prog is Acquisition, which simply has the best interface, and works (Core of LW). Arne Bab. - -- MacOSX: Ne gravas la rapideco, sed la sento. Esperanto: It's a vision and hopefully the future. Das Leben: Dir geht es nur deshalb so gut, weil du nicht weißt, wie es besser sein könnte. WebSeite: http://www.draketo.de (Esperanto: "kleiner drache") Wenn die Signatur dieser E-Mail verifizierbar ist, dann wurde ihr Inhalt auf dem Weg zu ihnen nicht verändert. (Infos: http://www.gnupg.org ) -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.2.1 (Darwin) iD8DBQE+6lwZMwdGm/6WxAQRAsM/AJ9uDGxKZYqpqSg7AO7Fgp1B4V4M0ACgtgk1 +2qOO6BsUWkzD0bXUIhZyWo= =dmwF -----END PGP SIGNATURE----- ________________________________________________________________________ Date: Mon, 16 Jun 2003 12:13:56 -0000 From: "jim_taylor_stockholm" Subject: Re: The files section is a mess --- In the_gdf@yahoogroups.com, "Vinnie" wrote: --- In the_gdf@yahoogroups.com, Raphael_Manfredi@p... wrote: Sorry, PARQ is part of Gnutella now. It is documented, it was reviewed, and it is implemented in a Gnutella servent (gtk-gnutella). That makes it part of the Gnutella world I don't think so. Just because one vendor implements something doesn't make it a working standard. In fact, single-vendor implementations should likely be excluded (I left out a lot of BearShare-onlyisms). Maybe there should be folders for protocols that are implemented by 1, 2, 3 vendors and so on. Thus the more popular protocols are given a "more implemented" status automatically. Other folders for protocols "currently" under discussion can be moderated by the GDF admin. Quite frankly, I feel that your interest in PARQ is egotistical and not technical, considering the mounting body of evidence that points to upload queues not improving download success rates. If Raph' is egotistical then you, Vincent are a beligerent liar. What mounting body of evidence!? Any "arguments" yourself and sidekick Dave have put up have been squashed. ________________________________________________________________________ ________________________________________________________________________ Message: 3 Date: Mon, 16 Jun 2003 10:30:20 -0400 From: "Dave Nicponski" Subject: RE: Re: The files section is a mess [Quote] Any "arguments" yourself and sidekick Dave have put up have been squashed. [/Quote] Sidekick? Jackass. I don't see anything that has been posted to counter my statements. You personal opinion aside, my technical statements stand unattacked, and even agreed/conceeded (some LimeWire guys) or partially so (Raph). Don't give me this crap. For the record, here are *YOUR* contributions to the discussion. [Quote] I am certain of PARQ's benefits now though and I hope it's powerful scalable queuing becomes another corner-stone of the Gnutella network. [/Quote] Great technical argument there. Glad you are "certain" about this. [Quote] Very good point Jay, **THE MOST PERFECT ANALOGY** does indeed imply that queues only ever fill up. As you say, we all agree that queuing will not solve the demand/supply problem and Dave's analogy clearly shows us that you have to wait longer the further back you are in the queue [/Quote] No, it doesn't. Had you read the post, and the analogy attached to it, you would see that there is a very real drain on the queues, and that there is a limit placed on overall queue growth. You probably didn't read it clearly, though. (*1*) But wait, you DID read it: [Quote] The extrapolation you neglect to include in your example for Active Queuing (the current system): DISCRETE TIME STEP 2000/10: (200 1/10 seconds later) Sent: 2000KB, Buffered: 100KB, Lost: 1900KB <== ~50% LOST! (as expected from initial specs :-/).. ..which means there is a massive amount of unmanaged (Lost!) demand flying round the network, which brings me to the second point I made, efficiency. [/Quote] Which, while correctly fitting the FORM of my analogy, is completely irrelevant to it. Recall, this was to illustrate the problem with essentially infinte, durable queues. Active queuing is not this. So, what was your excuse for the butchering in (*1*)? Who knows? [Quote] I love your pretty stars Dave, they make me smile. [/Quote] Yes, they make me smile as well. [Quote] Instead of real world examples or fantasy Post Offices try considering eMule again. I have heard many people say that it doesn't work. Well here's the first thing you should learn from this 1,000,000 user network - it DOES work. [/Quote] So, you say it works. The users say it doesn't. I have good evidence and reasoning to indicate that, in fact, it is not a Good Thing (TM). You are entitled to your opinion. I guess the final "vote" will be users, and which system they are happier with. If, in fact, the sampling of eMule users I have heard from is grossly non-representative, then you would have nothing to worry about. [Quote] May the best man 'win', of course :) [/Quote] Of course.... OK, so I see no "evidence" from you, that is real or otherwise, that would disprove ANY of the statements I made earlier. So much for being "generally debunked." Bah! -dave- ________________________________________________________________________ Date: Mon, 16 Jun 2003 15:35:12 -0000 From: "jim_taylor_stockholm" Subject: Re: The files section is a mess --- In the_gdf@yahoogroups.com, "Dave Nicponski" wrote: Sidekick? Jackass. I guess it's just Vinnie's manners - his friends come across as underlings. LOL No, it doesn't. Had you read the post, and the analogy attached to it, you would see that there is a very real drain on the queues, and that there is a limit placed on overall queue growth. You probably didn't read it clearly, though. Sounded like that was the first time you read my post, heh, ok, I know there is a length limit, the point is that there is a significant increase in length; and I read it clearly enough, thank you. [Quote] The extrapolation you neglect to include in your example for Active Queuing (the current system): DISCRETE TIME STEP 2000/10: (200 1/10 seconds later) Sent: 2000KB, Buffered: 100KB, Lost: 1900KB <== ~50% LOST! (as expected from initial specs :-/).. ..which means there is a massive amount of unmanaged (Lost!) demand flying round the network, which brings me to the second point I made, efficiency. [/Quote] Which, while correctly fitting the FORM of my analogy, is completely irrelevant to it. Read mosteo's posts, man. The relevant point I was making was that in congested situations the chance of one getting a download are left to chance because the requests are lost. A significant amount in your analogy. So, what was your excuse for the butchering ... As Vin might say (Sean Connery accent), "I don't mince my words" I love your pretty stars Dave, they make me smile. Yes, they make me smile as well. Well I'm glad I don't have a monopoly on facial expression. Phew (releived expression). So, you say it works. The users say it doesn't. Well The Users do say a lot of contradictory things. I must have a word with them. I dare say any sample you take of 1,000,000 will never be enough to judge. I have good evidence and reasoning to indicate that, in fact, it is not a Good Thing (TM). I go only on my own experience which hopefully means that the people with similar tastes are experiencing the same. The evidence is on my hard drive - evidence, such a crude word :). I have no special set-up and popular tastes so I say eMule Works Like a Charm (TM) and has done for years (hence the 1,000,000 users). So much for being "generally debunked." Nice to see you finally read my post, how about you do the other users the courtesy of the same and you will be, although there isn't much to debunk, queuing seems a relatively simple matter. ________________________________________________________________________ ________________________________________________________________________ Message: 7 Date: Mon, 16 Jun 2003 11:46:43 -0400 From: "Dave Nicponski" Subject: RE: Re: The files section is a mess [Quote] Nice to see you finally read my post, how about you do the other users the courtesy of the same and you will be, although there isn't much to debunk, queuing seems a relatively simple matter. [/Quote] Um, this is quite hard for me to parse, bu tI think you are saying that if I read everyone's posts, then my argument is "debunked"? Well, I have and did read all posts at the time they were posted, and I disagree still with your assessment. -dave- ________________________________________________________________________ ________________________________________________________________________ Message: 8 Date: Mon, 16 Jun 2003 11:55:00 -0400 From: "Greg Bildson" Subject: Snarkyness GDFers, As much as I love a little fighting match every now and then, lets try to stay a happy family and not fight needlessly. A lot of people still think that Gnutella is a crappy protocol so I think we have more to do. Openness isn't worth anything if we can't work together well. We have to bring people around to the benefits of an open protocol. To do that, it has to be clearly better. Thanks -greg [Non-text portions of this message have been removed] ________________________________________________________________________ ________________________________________________________________________ Message: 9 Date: Mon, 16 Jun 2003 17:55:12 +0200 From: "Mathias Bollaert" Subject: Re: Snarkyness Well said, greg =) M. ----- Original Message ----- From: "Greg Bildson" GDFers, As much as I love a little fighting match every now and then, lets try to stay a happy family and not fight needlessly. A lot of people still think that Gnutella is a crappy protocol so I think we have more to do. Openness isn't worth anything if we can't work together well. We have to bring people around to the benefits of an open protocol. To do that, it has to be clearly better. Thanks -greg [Non-text portions of this message have been removed] Yahoo! Groups Sponsor To unsubscribe from this group, send an email to: the_gdf-unsubscribe@egroups.com Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service. ________________________________________________________________________ ________________________________________________________________________ Message: 10 Date: Mon, 16 Jun 2003 16:19:44 -0000 From: "Vinnie" Subject: Re: Snarkyness --- In the_gdf@yahoogroups.com, "Greg Bildson" wrote: As much as I love a little fighting match every now and then, lets try to stay a happy family and not fight needlessly. Greg, I notice that no LimeWire representatives have commented on remote queues. Dave has given me pretty convincing arguments that remote queues don't do a whole lot to relieve the demand, or increase supply. What is your take on the matter? My objection to adding new queuing systems, or playing around with the one that we have, is based on Dave's "vestibule problem" observation, and our data in the labs. ________________________________________________________________________ ________________________________________________________________________ Message: 11 Date: Mon, 16 Jun 2003 16:21:01 -0000 From: "Vinnie" Subject: Re: The files section is a mess --- In the_gdf@yahoogroups.com, "jim_taylor_stockholm" wrote: I go only on my own experience which hopefully means that the people with similar tastes are experiencing the same. The evidence is on my hard drive - evidence, such a crude word :). I have no special set- up and popular tastes so I say eMule Works Like a Charm (TM) and has done for years (hence the 1,000,000 users). Well, KaZaA works like a "charm" and they don't have queues. ________________________________________________________________________ Date: Mon, 16 Jun 2003 16:25:31 -0000 From: "Vinnie" Subject: Re: The files section is a mess --- In the_gdf@yahoogroups.com, "jim_taylor_stockholm" wrote: --- In the_gdf@yahoogroups.com, "Dave Nicponski" wrote: Sidekick? Jackass. I guess it's just Vinnie's manners - his friends come across as underlings. LOL Well to be honest when Dave told me that remote queues didn't do much good I of course thought he was hallucinating or had no idea about what he was talking about in general. After since looking at the data, the behavior of upload servers whose queues are full, and considering the arguments presented against remote queues, I now have to agree. However, I will say this, that some of the arguments against remote queues don't apply when there are queues for different file sizes. I would be interested in an analysis of queuing behavior on the network when small/large (or more) queues exist. ________________________________________________________________________ Date: Mon, 16 Jun 2003 17:20:05 -0000 From: "jim_taylor_stockholm" Subject: Re: The files section is a mess --- In the_gdf@yahoogroups.com, "Vinnie" wrote: --- In the_gdf@yahoogroups.com, "jim_taylor_stockholm" wrote: I have no special set- up and popular tastes so I say eMule Works Like a Charm (TM) and has done for years (hence the 1,000,000 users). Well, KaZaA works like a "charm" and they don't have queues. Kazaa works, .. sometimes. Charmed, no, and the quality is far from that of other networks. Surprising considering there is ~5M of the little blighters. ________________________________________________________________________ ________________________________________________________________________ Message: 18 Date: Mon, 16 Jun 2003 13:37:57 -0400 From: "Dave Nicponski" Subject: RE: Re: The files section is a mess [Quote] Well to be honest when Dave told me that remote queues didn't do much good I of course thought he was hallucinating or had no idea about what he was talking about in general. [/Quote] Heh... -dave- ________________________________________________________________________ Date: Mon, 16 Jun 2003 18:22:46 -0000 From: "Adam Fisk" Subject: Re: remote queues I'm not sure what Greg's take on it is, but some of us were just talking the other day about how remote queues don't seem to have had much of an impact at all. Now that I think about it, it makes sense that they wouldn't have much of an effect. They're better than getting a busy, but not much. Not that I think we shouldn't use them, but I agree that it's not a very productive avenue to continue pursuing, as it will likely not lead to many more improvements. Push proxies and other optimizations (PFSP and DHTs) are far more important in my view. -Adam --- In the_gdf@yahoogroups.com, "Vinnie" wrote: --- In the_gdf@yahoogroups.com, "Greg Bildson" wrote: As much as I love a little fighting match every now and then, lets try to stay a happy family and not fight needlessly. Greg, I notice that no LimeWire representatives have commented on remote queues. Dave has given me pretty convincing arguments that remote queues don't do a whole lot to relieve the demand, or increase supply. What is your take on the matter? My objection to adding new queuing systems, or playing around with the one that we have, is based on Dave's "vestibule problem" observation, and our data in the labs. ________________________________________________________________________ Date: Mon, 16 Jun 2003 15:08:56 -0400 From: "Greg Bildson" Subject: RE: Re: remote queues I'm somewhat loath to try and wade back through your discussion (wasn't here at the time I believe). If there is a summary of the pros and cons, I would love to see it. I agree with Adam that PFSP and DHT (-like) features are probably more important. However, there is something to be said for queuing as well. I'm not sure what the cons you mentioned were other than perhaps too many connection attempts. The one major PRO that Mark likes over here is that queues encourage people to stick around. Being in position 708 might not be too useful but number 20 might. Staying on for 20 hours could be useful (although most users can't or won't stay on that long). I like queues because they are a good way of discouraging greedy clients from continuously sending out broadcast queries. If most resources are locked up in a queue, then you can't benefit by spamming more hosts or repeatedly trying to connect every minute or every few seconds. However, we can't have every client generating a lot of connection attempts for maintaining queue slots either. Thanks -greg -----Original Message----- From: Adam Fisk [mailto:afisk@limepeer.com] Sent: Monday, June 16, 2003 2:23 PM To: the_gdf@yahoogroups.com Subject: [the_gdf] Re: remote queues I'm not sure what Greg's take on it is, but some of us were just talking the other day about how remote queues don't seem to have had much of an impact at all. Now that I think about it, it makes sense that they wouldn't have much of an effect. They're better than getting a busy, but not much. Not that I think we shouldn't use them, but I agree that it's not a very productive avenue to continue pursuing, as it will likely not lead to many more improvements. Push proxies and other optimizations (PFSP and DHTs) are far more important in my view. -Adam